「BZOJ1016」[JSOI2008] 最小生成树计数
Description
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。
Input
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,000。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
Output
输出不同的最小生成树有多少个。你只需要输出数量对31011的模就可以了。
Sample Input
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
Sample Output
8
题解
就是不同的最小生成树方案，每种权值的边的数量是确定的，每种权值的边的作用是确定的
排序以后先做一遍最小生成树，得出每种权值的边使用的数量x
然后对于每一种权值的边搜索，得出每一种权值的边选择方案
然后乘法原理
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mod 31011 using namespace std; int n,m,cnt,tot,ans=1,sum; int fa[105]; struct edge{int x,y,v;}e[1005]; struct data{int l,r,v;}a[1005]; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } bool cmp(edge a,edge b){return a.v<b.v;} int find(int x){return x==fa[x]?x:find(fa[x]);} void dfs(int x,int now,int k) { if(now==a[x].r+1) { if(k==a[x].v)sum++; return; } int p=find(e[now].x),q=find(e[now].y); if(p!=q) { fa[p]=q; dfs(x,now+1,k+1); fa[p]=p;fa[q]=q; } dfs(x,now+1,k); } int main() { n=read();m=read(); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) e[i].x=read(),e[i].y=read(),e[i].v=read(); sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++) { if(e[i].v!=e[i-1].v){a[++cnt].l=i;a[cnt-1].r=i-1;} int p=find(e[i].x),q=find(e[i].y); if(p!=q){fa[p]=q;a[cnt].v++;tot++;} } a[cnt].r=m; if(tot!=n-1){printf("0");return 0;} for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=cnt;i++) { sum=0; dfs(i,a[i].l,0); ans=(ans*sum)%mod; for(int j=a[i].l;j<=a[i].r;j++) { int p=find(e[j].x),q=find(e[j].y); if(p!=q)fa[p]=q; } } printf("%d",ans); return 0; } |
计数器 9787365
OI 课件=>
OI 课件=>
“每种权值的边的作用是确定的”，作用是什么意思？？
蛤
笨笨的问一句,为什么不能路径压缩
合并连通块时压缩就不能方便地分开连通块
楼主好人