多彩路径计数(Paths) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    if (!(cin >> n >> m >> k)) return 0;
    vector<int> col(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> col[i];
        --col[i];
    }
    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].first >> edges[i].second;
    }
    int tot = 1 << k;
    vector<vector<long long>> dp(tot, vector<long long>(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        dp[1 << col[i]][i] = 1;
    }
    vector<vector<int>> masksByPop(k + 1);
    for (int mask = 1; mask < tot; ++mask) {
        masksByPop[__builtin_popcount(mask)].push_back(mask);
    }
    long long ans = 0;
    for (int pc = 2; pc <= k; ++pc) {
        for (int mask : masksByPop[pc]) {
            for (const auto& e : edges) {
                int u = e.first, v = e.second;
                if (((mask >> col[u]) & 1) && ((mask >> col[v]) & 1)) {
                    dp[mask][u] += dp[mask ^ (1 << col[u])][v];
                    dp[mask][v] += dp[mask ^ (1 << col[v])][u];
                }
            }
            for (int i = 1; i <= n; ++i) ans += dp[mask][i];
        }
    }
    cout << ans << "\n";
    return 0;
}