首页 > 代码库 > HDU 4408 - Minimum Spanning Tree
HDU 4408 - Minimum Spanning Tree
题解：
Kruskal 算法的基本思想是，按照边长排序，然后不断将短边加入集合，最终一步如果能成功把 n-1 条边都加入同一个集合，则找到了最小生成树。在维护集合时，可以使用并查集来快速处理。
如果把 Kruskal 的过程按照边长划分成多个阶段，实际上是处理了所有短边的连通性之后继续处理下一个长度的边的连通性，并依次继续处理剩下边的连通性。
然后我们可以发现，不同长度的边之间的连通性互不影响。
假设存在 n1 条长度为 c1 的边，n2 条长度为 c2 的边… 则 Kruskal 首先处理 c1 边的连通性，然后处理 c2 边的连通性。
对于 c1 边的连通性的处理可能有多种方案，即从 n1 条边中取出一定数量的边构成最大连通图，但是最终处理完之后的结果对于 c2 来说是完全一样的。
因此算法就出来了，在 Kruskal 的基础上，使用 Matrix-Tree 定理处理每个阶段生成树的种数，最后将所有阶段的结果相乘即可。
以上转自http://jcf94.com/2014/11/03/2014-11-03-HDU-4408/
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 #include <algorithm> 6 using namespace std; 7 #define LL long long 8 const int MAXN = 105; 9 const int MAXM = 1005; 10 struct Matrix { 11 LL mat[MAXN][MAXN]; 12 void init() { 13 memset(mat, 0, sizeof(mat)); 14 } 15 LL det(int n, LL MOD) 16 { 17 for (int i = 0; i < n; i++) 18 for (int j = 0; j < n; j++) 19 mat[i][j] = (mat[i][j] % MOD + MOD) % MOD; 20 LL res = 1; 21 for (int i = 0; i < n; i++) 22 { 23 for (int j = i+1; j < n; j++) 24 { 25 while (mat[j][i]) 26 { 27 LL t = mat[i][i] / mat[j][i]; 28 for (int k = i; k < n; k++) 29 { 30 mat[i][k] = (mat[i][k] - t*mat[j][k]) % MOD; 31 swap(mat[i][k], mat[j][k]); 32 } 33 res = -res; 34 } 35 } 36 res = res * mat[i][i] % MOD; 37 } 38 return (res+MOD) % MOD; 39 } 40 }ret; 41 int g[MAXN][MAXN]; 42 struct Edge { 43 int u, v, w; 44 Edge() {} 45 Edge(int a, int b): u(a), v(b) {} 46 friend bool operator < (Edge a, Edge b) { 47 return a.w < b.w; 48 } 49 }edge[MAXM]; 50 int f[MAXN]; 51 int sf(int x){ 52 return x == f[x] ? x : f[x] = sf(f[x]); 53 } 54 int Belong[MAXN], tot; 55 namespace SV //处理单层 56 { 57 vector<Edge> edge; 58 vector<int> node; 59 int f[MAXN];//寻找连通分量 60 int sf(int x) { 61 return x == f[x] ? x : f[x] = sf(f[x]); 62 } 63 int id[MAXN]; 64 LL solve(int n, LL MOD) 65 { 66 for (int i = 0; i < n; i++) f[i] = i; 67 LL res = 1; 68 for (int i = 0; i < edge.size(); i++) 69 { 70 f[sf(edge[i].u)] = sf(edge[i].v); 71 } 72 for (int i = 0; i < n; i++) 73 { 74 if (sf(i) == i)//处理同一连通分量 75 { 76 node.clear(); 77 memset(g, 0, sizeof(g)); 78 memset(id, -1, sizeof(id)); 79 ret.init(); 80 for (int j = 0; j < n; j++) 81 if (sf(j) == i) node.push_back(j); 82 for (int j = 0; j < node.size(); j++) 83 id[node[j]] = j; 84 for (int j = 0; j < edge.size(); j++) 85 { 86 if (id[edge[j].u] == -1 || id[edge[j].v] == -1) continue; 87 int u = id[edge[j].u], v = id[edge[j].v]; 88 g[u][v]++, g[v][u]++; 89 } 90 int cnt = node.size();//点数 91 for (int j = 0; j < cnt; j++) 92 for (int k = 0; k < cnt; k++) 93 if (j != k && g[j][k] > 0) 94 ret.mat[j][j] += g[j][k], ret.mat[j][k] = -g[j][k]; 95 res = res*ret.det(cnt-1, MOD) % MOD; 96 } 97 } 98 return res%MOD; 99 }100 }101 int n, m;102 LL MOD;103 LL ans;104 int main()105 {106 while (~scanf("%d%d%lld", &n, &m, &MOD) && (n+m+MOD))107 {108 for (int i = 1; i <= n; i++) f[i] = i;109 for (int i = 1; i <= m; i++)110 {111 scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);112 }113 sort(edge+1, edge+m+1);114 ans = 1;115 for (int st = 1; st <= m;)116 {117 int ed = st;118 while (ed <= m && edge[ed].w == edge[st].w) ed++;119 tot = 0;120 for (int i = 1; i <= n; i++)121 if (sf(i) == i) Belong[i] = tot++;//计数连通块 122 for (int i = 1; i <= n; i++)123 Belong[i] = Belong[sf(i)];124 SV::edge.clear();125 for (int i = st; i < ed; i++)126 {127 int u = edge[i].u, v = edge[i].v;128 if (sf(u) == sf(v)) continue;129 SV::edge.push_back(Edge(Belong[u], Belong[v]));//子问题存边 130 }131 ans = ans * SV::solve(tot, MOD) % MOD;132 for (int i = st; i < ed; i++)133 {134 int u = edge[i].u, v = edge[i].v;135 f[sf(u)] = sf(v);136 }137 st = ed;138 }139 int cnt = 0;140 for (int i = 1; i <= n; i++)141 if (sf(i) == i) cnt++;142 if (cnt > 1) puts("0");143 else printf("%lld\n", ans%MOD);144 }145 }
HDU 4408 - Minimum Spanning Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。