这题做法好玄妙啊。。
直接上结论:对于每一种权值的所有边,其在最小生成树中的作用是固定的
也就是先求一遍最小生成树,然后对于每一种权值的边,记录他们对于最小生成树的贡献。那么对于从小到大枚举所有权值的边,枚举这一种权值中所有边选/不选,判断贡献是否与一开始的最小生成树中的相同。然后乘起来就可以了。
听说还可以用基尔霍夫矩阵。。去学了一下这个东西好像还挺好懂。。
好玄妙啊。。
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 68 69 70 71 72 73 74 |
// <1016.cpp> - 05/18/16 19:16:01 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=110,MAXM=1010; const int INF=1e9; const int MOD=31011; struct edge{ int a,b,c; bool operator <(const edge y) const{return c<y.c;} }e[MAXM]; struct block{ int l,r,v; }b[MAXM]; int tot; int f[MAXN]; int gf(int x){return x==f[x]?x:gf(f[x]);} int num; void dfs(int x,int now,int k){ if(now==b[x].r+1){ if(k==b[x].v)num++; return; } int fa=gf(e[now].a),fb=gf(e[now].b); if(fa!=fb){ f[fa]=fb; dfs(x,now+1,k+1); f[fa]=fa;f[fb]=fb; } dfs(x,now+1,k); } int main(){ int n=gi(),m=gi(); for(int i=1;i<=m;i++)e[i].a=gi(),e[i].b=gi(),e[i].c=gi(); sort(e+1,e+m+1); for(int i=1;i<=n;i++)f[i]=i; int cnt=0; for(int i=1;i<=m;i++){ if(e[i].c!=e[i-1].c){b[tot].r=i-1;b[++tot].l=i;} int fa=gf(e[i].a),fb=gf(e[i].b); if(fa!=fb){f[fa]=fb;b[tot].v++;cnt++;} } b[tot].r=m; if(cnt!=n-1){putchar('0');return 0;} for(int i=1;i<=n;i++)f[i]=i; int ans=1; for(int i=1;i<=cnt;i++){ num=0; dfs(i,b[i].l,0); ans=ans*num%MOD; for(int j=b[i].l;j<=b[i].r;j++){ int fa=gf(e[j].a),fb=gf(e[j].b); if(fa!=fb)f[fa]=fb; } } printf("%d",ans); return 0; } |