Visits: 255

ARC093E Bichrome Spanning Tree

题意

• 给定一张 $n$ 个点 $m$ 条边的无重边无自环的无向图，边有边权。
• 求给边染黑白两色，使得包含两种颜色的边的边权和最小的生成树的边权和恰好为 $X$ 的方案数。
• $n \le 10^3$，$m \le 2 \times 10^3$，答案对 $10^9+7$ 取模。

题解

首先求出 MST 的边权和 $W$。

如果 $W>X$ 显然无解，以下不考虑这种情况。

显然最终的包含两种颜色的边的边权和最小的生成树要么就是 MST（要求 $W = X$，方案数为 $(2^{n-1}-2)\cdot 2^{m-n+1}$），要么 MST 里的边全都是同一种颜色，然后找到一条与这种颜色不同的边 $(u,v)$，用这条边替换 MST 中 $u,v$ 之间的最大边权，使得替换后的边权和最小。

因此我们要求出有多少条边替换后会使边权和 $< X,=X,>X$，设个数分别为 $a,b,c$，则这种情况的方案数为 $(2^b-1)2^{c+1}$。

设 $n,m$ 同阶，总时间复杂度可以做到 $\mathcal O(n \log n)$，但本题 $\mathcal O(n^2)$ 即可通过。

代码

const int N = 1e3 + 7, inf = 1 << 30;
int n, m, a[N][N], d[N], f[N];
bool v[N], u[N][N];
ll X, W;
vi e[N];
modint ans;

inline void prim() {
    for (int i = 0; i <= n; i++) d[i] = inf;
    d[1] = 0;
    for (int i = 1; i <= n; i++) {
        int x = 0;
        for (int j = 1; j <= n; j++)
            if (!v[j] && d[j] < d[x]) x = j;
        v[x] = 1, W += d[x];
        if (f[x])
            e[x].pb(f[x]), e[f[x]].pb(x),
            u[x][f[x]] = u[f[x]][x] = 1;
        for (int y = 1; y <= n; y++)
            if (!v[y] && d[y] > a[x][y])
                d[y] = a[x][y], f[y] = x;
    }
}

int dfs(int x, int f, int z) {
    for (int y : e[x])
        if (y != f) {
            if (y == z) return a[x][y];
            int ret = dfs(y, x, z);
            if (ret) return max(ret, a[x][y]);
        }
    return 0;
}

int main() {
    rd(n, m), rd(X);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = inf;
    for (int i = 1; i <= n; i++) a[i][i] = 0;
    for (int i = 1, x, y, z; i <= m; i++)
        rd(x, y, z), a[x][y] = a[y][x] = min(a[x][y], z);
    prim();
    if (W > X) return print(0), 0;
    if (W == X) ans = ((modint)2 ^ m) - ((modint)2 ^ (m - n + 2));
    int b = 0, c = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (a[i][j] < inf && !u[i][j]) {
                ll K = W + a[i][j] - dfs(i, 0, j);
                if (K == X) ++b;
                if (K > X) ++c;
            }
    ans += ((modint)2 ^ (b + c + 1)) - ((modint)2 ^ (c + 1));
    print(ans);
    return 0;
}