首页 > 代码库 > 最小生成树计数
最小生成树计数
Minimum Spanning Tree http://acm.hdu.edu.cn/showproblem.php?pid=4408
模板题
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 #define mt(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 typedef __int64 LL; 8 class MinST_count { ///最小生成树计数 9 typedef int typec;///边权的类型 10 static const int ME=1024;///边的个数 11 static const int MV=128;///点的个数 12 struct E { 13 int u,v; 14 typec w; 15 friend bool operator <(E a,E b) { 16 return a.w<b.w; 17 } 18 } e[ME]; 19 LL mod,ans,mat[MV][MV]; 20 int n,le,fa[MV],ka[MV],gk[MV][MV]; 21 bool vis[MV]; 22 vector<int> gra[MV]; 23 int getroot(int a,int b[]) { 24 return a==b[a]?a:b[a]=getroot(b[a],b); 25 } 26 LL det(LL a[][MV],int n) { ///生成树计数 27 for(int i=0; i<n; i++) 28 for(int j=0; j<n; j++) 29 a[i][j]%=mod; 30 LL ret=1; 31 for(int i=1; i<n; i++) { 32 for(int j=i+1; j<n; j++) { 33 while(a[j][i]) { 34 LL t=a[i][i]/a[j][i]; 35 for(int k=i; k<n; k++) 36 a[i][k]=(a[i][k]-a[j][k]*t)%mod; 37 for(int k=i; k<n; k++) 38 swap(a[i][k],a[j][k]); 39 ret=-ret; 40 } 41 } 42 if(!a[i][i]) return 0; 43 ret=ret*a[i][i]%mod; 44 } 45 return (ret+mod)%mod; 46 } 47 public: 48 void init(int tn,int tmod) { ///传入点的个数，%tmod，点下标1开始 49 n=tn; 50 mod=tmod; 51 le=0; 52 mt(fa,0); 53 mt(ka,0); 54 mt(vis,0); 55 mt(gk,0); 56 mt(mat,0); 57 } 58 void add(int u,int v,typec w) { 59 e[le].u=u; 60 e[le].v=v; 61 e[le].w=w; 62 le++; 63 } 64 LL solve() {///返回生成树个数%mod 65 sort(e,e+le); 66 for(int i=1; i<=n; i++){ 67 fa[i]=i; 68 vis[i]=false; 69 gra[i].clear(); 70 } 71 typec pre=-1; 72 ans=1; 73 for(int h=0; h<=le; h++) { 74 if(e[h].w!=pre||h==le) { ///一组边加完 75 for(int i=1; i<=n; i++) { 76 if(vis[i]) { 77 int u=getroot(i,ka); 78 gra[u].push_back(i); 79 vis[i]=false; 80 } 81 } 82 for(int i=1; i<=n; i++) { ///枚举每个联通分量 83 if(gra[i].size()>1) { 84 mt(mat,0); 85 int len=gra[i].size(); 86 for(int a=0; a<len; a++) { ///构建矩阵 87 for(int b=a+1; b<len; b++) { 88 LL la=gra[i][a],lb=gra[i][b]; 89 mat[a][b]=(mat[b][a]-=gk[la][lb]); 90 mat[a][a]+=gk[la][lb]; 91 mat[b][b]+=gk[la][lb]; 92 } 93 } 94 LL ret=(LL)det(mat,len); 95 ans=(ans*ret)%mod; 96 for(int a=0; a<len; a++) 97 fa[gra[i][a]]=i; 98 } 99 }100 for(int i=1; i<=n; i++) {101 ka[i]=fa[i]=getroot(i,fa);102 gra[i].clear();103 }104 if(h==le)break;105 pre=e[h].w;106 }107 int a=e[h].u;108 int b=e[h].v;109 int pa=getroot(a,fa);110 int pb=getroot(b,fa);111 if(pa==pb)continue;112 vis[pa]=vis[pb]=true;113 ka[getroot(pa,ka)]=getroot(pb,ka);114 gk[pa][pb]++;115 gk[pb][pa]++;116 }117 for(int i=2; i<=n&&ans; i++)118 if(ka[i]!=ka[i-1])119 ans=0;120 ans=(ans+mod)%mod;121 return ans;122 }123 }gx;124 int main() {125 int n,m,p;126 while(~scanf("%d%d%d",&n,&m,&p),n|m|p) {127 gx.init(n,p);128 while(m--) {129 int u,v,w;130 scanf("%d%d%d",&u,&v,&w);131 gx.add(u,v,w);132 }133 printf("%I64d\n",gx.solve());134 }135 return 0;136 }
1016: [JSOI2008]最小生成树计数 http://www.lydsy.com/JudgeOnline/problem.php?id=1016
一样
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 #define mt(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 typedef long long LL; 8 class MinST_count { ///最小生成树计数 9 typedef int typec;///边权的类型 10 static const int ME=1024;///边的个数 11 static const int MV=128;///点的个数 12 struct E { 13 int u,v; 14 typec w; 15 friend bool operator <(E a,E b) { 16 return a.w<b.w; 17 } 18 } e[ME]; 19 LL mod,ans,mat[MV][MV]; 20 int n,le,fa[MV],ka[MV],gk[MV][MV]; 21 bool vis[MV]; 22 vector<int> gra[MV]; 23 int getroot(int a,int b[]) { 24 return a==b[a]?a:b[a]=getroot(b[a],b); 25 } 26 LL det(LL a[][MV],int n) { ///生成树计数 27 for(int i=0; i<n; i++) 28 for(int j=0; j<n; j++) 29 a[i][j]%=mod; 30 LL ret=1; 31 for(int i=1; i<n; i++) { 32 for(int j=i+1; j<n; j++) { 33 while(a[j][i]) { 34 LL t=a[i][i]/a[j][i]; 35 for(int k=i; k<n; k++) 36 a[i][k]=(a[i][k]-a[j][k]*t)%mod; 37 for(int k=i; k<n; k++) 38 swap(a[i][k],a[j][k]); 39 ret=-ret; 40 } 41 } 42 if(!a[i][i]) return 0; 43 ret=ret*a[i][i]%mod; 44 } 45 return (ret+mod)%mod; 46 } 47 public: 48 void init(int tn,int tmod) { ///传入点的个数，%tmod，点下标1开始 49 n=tn; 50 mod=tmod; 51 le=0; 52 mt(fa,0); 53 mt(ka,0); 54 mt(vis,0); 55 mt(gk,0); 56 mt(mat,0); 57 } 58 void add(int u,int v,typec w) { 59 e[le].u=u; 60 e[le].v=v; 61 e[le].w=w; 62 le++; 63 } 64 LL solve() {///返回生成树个数%mod 65 sort(e,e+le); 66 for(int i=1; i<=n; i++){ 67 fa[i]=i; 68 vis[i]=false; 69 gra[i].clear(); 70 } 71 typec pre=-1; 72 ans=1; 73 for(int h=0; h<=le; h++) { 74 if(e[h].w!=pre||h==le) { ///一组边加完 75 for(int i=1; i<=n; i++) { 76 if(vis[i]) { 77 int u=getroot(i,ka); 78 gra[u].push_back(i); 79 vis[i]=false; 80 } 81 } 82 for(int i=1; i<=n; i++) { ///枚举每个联通分量 83 if(gra[i].size()>1) { 84 mt(mat,0); 85 int len=gra[i].size(); 86 for(int a=0; a<len; a++) { ///构建矩阵 87 for(int b=a+1; b<len; b++) { 88 LL la=gra[i][a],lb=gra[i][b]; 89 mat[a][b]=(mat[b][a]-=gk[la][lb]); 90 mat[a][a]+=gk[la][lb]; 91 mat[b][b]+=gk[la][lb]; 92 } 93 } 94 LL ret=(LL)det(mat,len); 95 ans=(ans*ret)%mod; 96 for(int a=0; a<len; a++) 97 fa[gra[i][a]]=i; 98 } 99 }100 for(int i=1; i<=n; i++) {101 ka[i]=fa[i]=getroot(i,fa);102 gra[i].clear();103 }104 if(h==le)break;105 pre=e[h].w;106 }107 int a=e[h].u;108 int b=e[h].v;109 int pa=getroot(a,fa);110 int pb=getroot(b,fa);111 if(pa==pb)continue;112 vis[pa]=vis[pb]=true;113 ka[getroot(pa,ka)]=getroot(pb,ka);114 gk[pa][pb]++;115 gk[pb][pa]++;116 }117 for(int i=2; i<=n&&ans; i++)118 if(ka[i]!=ka[i-1])119 ans=0;120 ans=(ans+mod)%mod;121 return ans;122 }123 }gx;124 int main() {125 int n,m,p;126 while(~scanf("%d%d",&n,&m)) {127 gx.init(n,31011);128 while(m--) {129 int u,v,w;130 scanf("%d%d%d",&u,&v,&w);131 gx.add(u,v,w);132 }133 printf("%lld\n",gx.solve());134 }135 return 0;136 }
end
最小生成树计数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。