P2143 [JSOI2010] 巨额奖金 题解

P2143 [JSOI2010] 巨额奖金 题解

矩阵树定理+Kruskal

最小生成树计数。

思路

MST 都是喵喵题。

引理 1：所有合法的权值相同边的连边方案，得到的连通块情况是相同的。

感性理解：如果不相同意味着至少有一条边可以连通一对连通块。

所以我们可以这么做：先跑 Kruskal 标记树边，然后枚举边权，对于同一边权的树边先删掉，所有剩余的图用并查集缩点，之后加入当前边权的边，缩点后图的生成树个数就是当前边权边的放置方案，根据引理，每个边权贡献独立，所以乘法原理即可。

注意每次要把所有的非当前边权的树边加入，否则可能导致图不连通。

时间复杂度：\(O(n^3)\)。

// Problem: P4208 [JSOI2008] 最小生成树计数
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-02 13:29:52#include <algorithm>
#include <iostream>
#include <map>
#define int long long
using namespace std;
const int N = 200 + 10, mod = 31011;int n, m, lap[N][N], fa[N];
struct qwq {int u, v, w;
} e[1010];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
void merge(int a, int b) {int x = find(a), y = find(b);if(x == y) return ;fa[x] = y;
}
int tot;
map<int, int> h;
int id(int x) {if(h.count(x)) return h[x];return h[x] = ++ tot;
}
void add(int a, int b) {lap[a][a] ++, lap[b][b] ++, lap[a][b] --, lap[b][a] --;
}
int det(int n) {int c = 1;for(int i = 1; i < n; i ++)for(int j = i + 1; j < n; j ++)while(lap[j][i]) {int d = lap[i][i] / lap[j][i];for(int k = i; k < n && d; k ++)lap[i][k] = (lap[i][k] - 1ll * d * lap[j][k] % mod) % mod;swap(lap[i], lap[j]), c = -c;}for(int i = 1; i < n; i ++) c = 1ll * c * lap[i][i] % mod;return (c + mod) % mod;
}
void clear() {for(int i = 1; i <= tot; i ++)for(int j = 1; j <= tot; j ++)lap[i][j] = 0;tot = 0; h.clear();
}
bool ok[1010];
void kruskal() {for(int i = 1; i <= n; i ++) fa[i] = i;for(int i = 1; i <= m; i ++) {int x = find(e[i].u), y = find(e[i].v);if(x != y) fa[x] = y, ok[i] = 1;}
}signed main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1; i <= m; i ++)cin >> e[i].u >> e[i].v >> e[i].w;sort(e + 1, e + m + 1, [](qwq a, qwq b) {return a.w < b.w;});int ans = 1;kruskal();for(int i = 1, j = 0; i <= m; i = j + 1) {clear();for(int i = 1; i <= n; i ++) fa[i] = i;j = i;while(j < m && e[j + 1].w == e[i].w) j ++;for(int k = 1; k < i; k ++) if(ok[k]) merge(e[k].u, e[k].v);for(int k = j + 1; k <= m; k ++) if(ok[k]) merge(e[k].u, e[k].v);for(int k = i; k <= j; k ++) {int x = find(e[k].u), y = find(e[k].v);if(x != y) add(id(x), id(y));}for(int k = i; k <= j; k ++)merge(e[k].u, e[k].v);ans = 1ll * ans * det(tot) % mod;}for(int i = 1; i < n; i ++) if(find(i) != find(i + 1)) return cout << 0, 0;cout << ans << '\n';return 0;
}