随机颜色编码

随机颜色编码（Color Coding）是由 Noga Alon 等人在 1995 年提出的一种极其天才的算法技巧。它的出现，几乎就是为了解决一类特定的“老大难”图论问题：在一个巨大的图中，寻找一个特定形状的“小结构”（且要求不能走回头路/节点不能重复）。

引言

想象你正在一个包含 个景点、 条道路的巨大风景区骑马。每个景点都有一个“花韵值”。你需要规划一条满足以下三个条件的路线：

  1. 不走回头路（简单路径）： 任何景点最多只能经过一次。

  2. 雅致要求： 途经所有景点的“花韵值总和”，必须恰好是数字 () 的倍数。

  3. 最省体力： 在满足前两点的基础上，骑马消耗的总体力最少。

对于这个问题，我们首先需要 get 到的点是，根据鸽巢原理，满足这些条件的简单路径，点的个数一定小于等于 。因为，从某个点作为起点出发，如果路径上到达两个点的前缀和同余，那么说明这两个点的中间的这一段的“花韵值总和”一定是 的倍数。

所以问题变成了，从这个图中找到一个小于等于 个点的简单路径，要求“花韵值之和”是 的倍数，并且要求路程最短。

若我们尝试用 dfs 来解决这个问题，遇到题目给了“菊花图”，显然会超时。而若我们尝试用dijkstra来解决问题，dij只会一味的记录最短路径，无法体现路径上选了节点的值总和，而如果我们用分层图的dijkstra呢？我们需要表示的状态有路径上的和，选择过的点和，以及一个数值，最短路程。此时空间复杂度来到了 ，显然无法满足。

对于这种“大图找小结构”的死局，我们需要请出一个及其优雅的算法科技——随机颜色编码（Color Coding）

核心思想

为什么普通的图论算法无法解决“不走回头路”，因为表示每个节点的是它的下标，这会导致表示是否走过的状态数极其庞大（“大图”：）

而既然这道题的 那么小（“小结构”），我们干脆给图中的一万个节点随机分配 这 种颜色。

把寻找 个不同的节点变为寻找 种不同的颜色，这样的话，状态表示一瞬间就从 变为 。

我们发现，有很多状态是冲突的，比如，如果有两个相同颜色的点，他们无法同时被放入一个结构中，这会导致一些状态没有被考虑。那么它的成功率是多少呢？假设任取 个点，让这 个点颜色互不相同的概率是 。

为了让它命中正确答案，可以做 次随机化的操作，这样的话，冲突的概率只有 ，微乎其微了。

我们经过条件转化之后，做一个状压DP，时间复杂度为，具体做法是从小到大枚举选择了的颜色的状态，然后枚举所有边，进行状态转移。

最后总的时间复杂度是 ，此题看似会TLE，但是思路是对了的，通过剪枝可以通过这道题。

特性优化

之前的做法是随机颜色编码的标准做法，适用范围广，但是单次的时间复杂度比较大，有 种状态需要考虑。因此有一种做法名为“2-染色法”，可以解决这种线性路径的问题。

对所有的点进行随机染色，只是染色的种类不再是 种，而是 与 两种。

不去记录 种复杂的混色状态，只是将路径劈开，让路径一半都为 ，另一半都为 。

接着进行DP，要求从每个点只能走同色的点，并且经过的点的个数不能超过 ，再按照模 的余数进行分类，得到每种余数的只经过 个同色点的路径的最小值，若从点 出发，余数为 ，小于等于 个同色点的最小路程值表示为 。

然后再将其在边界上合并，对于点 ，枚举有边连接的异色节点 ，可以作为答案的就是 。

那么，2-染色法的命中率是多少呢？对于一条合法的最优路径，其符合条件概率最小为 ，经过计算，当进行 次随机染色操作的时候，未命中的概率低于 ，我们采取 次。

最后，其时间复杂度为 。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 rnd(233);

const int INF = 1e9 + 10;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++) cin >> a[i], a[i] %= k;
    vector<vector<array<ll, 2>>> adj(n + 1);
    int u, v, w;
    for (int i = 0; i < m; i ++) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w}), adj[v].push_back({u, w});
    }
    for (int i = 1; i <= n; i ++) {
        if (!a[i]) {
            cout << "0\n";
            return;
        }
    }

    vector<int> col(n + 1);
    vector<vector<vector<array<ll, 2>>>> edge(n + 1, vector<vector<array<ll, 2>>>(k, vector<array<ll, 2>>(2, array<ll, 2>{LLONG_MAX, 0})));
    vector<vector<ll>> dp(n + 1, vector<ll>(k, LLONG_MAX));

    ll ans = LLONG_MAX;
    for (int i = 0; i < 250; i ++) {
        for (int j = 1; j <= n; j ++) col[j] = rnd() & 1;
        for (int u = 1; u <= n; u ++) {
            for (int j = 0; j < k; j ++) {
                dp[u][j] = LLONG_MAX;
                edge[u][j][0] = {LLONG_MAX, 0};
                edge[u][j][1] = {LLONG_MAX, 0};
            }
        }
        
        for (int u = 1; u <= n; u ++) {
            for (auto& [v, w] : adj[u]) {
                if (col[u] == col[v]) {
                    int q = (a[v] + a[u]) % k;
                    if (w <= edge[v][q][0][0]) swap(edge[v][q][0], edge[v][q][1]), edge[v][q][0] = {w, u};
                    else if (w <= edge[v][q][1][0]) edge[v][q][1] = {w, u};
                }
            }
        }
        for (int u = 1; u <= n; u ++) {
            dp[u][a[u] % k] = 0;
            for (auto& [v, w] : adj[u]) {
                if (col[u] == col[v]) {
                    dp[u][(a[u] + a[v]) % k] = min(dp[u][(a[u] + a[v]) % k], w);
                    for (int j = 0; j < k; j ++) {
                        int q = (j + a[u]) % k;
                        if (edge[v][j][0][0] != LLONG_MAX) {
                            if (edge[v][j][0][1] != u) {
                                dp[u][q] = min(dp[u][q], edge[v][j][0][0] + w);
                            } else if (edge[v][j][1][0] != LLONG_MAX) {
                                dp[u][q] = min(dp[u][q], edge[v][j][1][0] + w);
                            }
                        }
                    }
                }
            }
        }

        for (int u = 1; u <= n; u ++) {
            for (auto& [v, w] : adj[u]) {
                if (col[u] != col[v] && u > v) {
                    for (int j = 0; j < k; j ++) {
                        if (dp[u][j] != LLONG_MAX && dp[v][(k - j) % k] != LLONG_MAX) {
                            ans = min(ans, dp[u][j] + dp[v][(k - j) % k] + w);
                        }
                    }
                }
            }
        }
    }

    cout << (ans == LLONG_MAX ? -1 : ans) << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t --) {
        solve();
    }

    return 0;
}