首页 > 代码库 > BZOJ 1016: [JSOI2008]最小生成树计数
BZOJ 1016: [JSOI2008]最小生成树计数
http://www.lydsy.com/JudgeOnline/problem.php?id=1016
题意：
思路：
一个无向图所有的最小生成树中某种权值的边的数目均相同。
引用一篇大牛的证明：
我们证明以下定理：一个无向图所有的最小生成树中某种权值的边的数目均相同。
开始时，每个点单独构成一个集合。
首先只考虑权值最小的边，将它们全部添加进图中，并去掉环，由于是全部尝试添加，那么只要是用这种权值的边能够连通的点，最终就一定能在一个集合中。
那么不管添加的是哪些边，最终形成的集合数都是一定的，且集合的划分情况一定相同。那么真正添加的边数也是相同的。因为每添加一条边集合的数目便减少1.
那么权值第二小的边呢？我们将之间得到的集合每个集合都缩为一个点，那么权值第二小的边就变成了当前权值最小的边，也有上述的结论。
因此每个阶段，添加的边数都是相同的。我们以权值划分阶段，那么也就意味着某种权值的边的数目是完全相同的。
所以先用克鲁斯卡尔算法计算一遍最小生成树，统计每一权值的边组需要加几条边，最后暴搜，乘法原理相乘即可。注意，要判断无法连通的情况。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,ll> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn=10000+5; 17 const int mod=31011; 18 19 struct node 20 { 21 int u,v,w; 22 }e[10*maxn]; 23 24 struct node2 25 { 26 int l,r; 27 int c; 28 }a[maxn]; 29 30 int n, m; 31 int sum; 32 int cnt,tot; 33 int p[maxn]; 34 35 bool cmp(node a, node b) 36 { 37 return a.w<b.w; 38 } 39 40 int find(int x) 41 { 42 return x==p[x]?x:find(p[x]); 43 } 44 45 void dfs(int cur, int num ,int pos) 46 { 47 if(pos>a[cur].r) 48 { 49 if(num==a[cur].c) sum++; 50 return; 51 } 52 int x=find(e[pos].u); 53 int y=find(e[pos].v); 54 if(x!=y) 55 { 56 p[x]=y; 57 dfs(cur,num+1,pos+1); 58 p[x]=x; 59 } 60 dfs(cur,num,pos+1); 61 } 62 63 int main() 64 { 65 //freopen("in.txt","r",stdin); 66 while(~scanf("%d%d",&n,&m)) 67 { 68 for(int i=1;i<=n;i++) p[i]=i; 69 for(int i=1;i<=m;i++) 70 scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); 71 72 sort(e+1,e+m+1,cmp); 73 cnt=0; tot=0; 74 for(int i=1;i<=m;i++) 75 { 76 if(e[i].w!=e[i-1].w) 77 { 78 a[++cnt].l=i; 79 a[cnt-1].r=i-1; 80 a[cnt].c=0; 81 } 82 int x=find(e[i].u); 83 int y=find(e[i].v); 84 if(x!=y) 85 { 86 p[x]=y; 87 a[cnt].c++; 88 tot++; 89 } 90 } 91 a[cnt].r=m; 92 93 if(tot!=n-1) //连不起来的情况 94 { 95 printf("0\n"); 96 continue; 97 } 98 99 100 for(int i=1;i<=n;i++) p[i]=i;101 int ans=1;102 for(int i=1;i<=cnt;i++)103 {104 sum=0;105 dfs(i,0,a[i].l);106 ans=(ans*sum)%mod;107 for(int j=a[i].l;j<=a[i].r;j++)108 {109 int x=find(e[j].u);110 int y=find(e[j].v);111 if(x!=y) p[x]=y;112 }113 }114 printf("%d\n",ans);115 }116 return 0;117 }
BZOJ 1016: [JSOI2008]最小生成树计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。