首页 > 代码库 > BZOJ1016 JSOI2008 最小生成树计数 生成树+DFS
BZOJ1016 JSOI2008 最小生成树计数 生成树+DFS
题意：求最小生成树的方案数，保证每个边权出现的次数小于十次。
题解：首先我们需要知道：一张图对于一个确定的边权，在任意最小生成树中出现的次数是相同的（请不要问我为什么QAQ）。所以我们先求出每一种边权在MST中出现的次数，然后枚举每一个边权，暴力看取哪些边可以组出一颗MST，复杂度O(M*2^10*M/10)
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int Mod=31011;const int MAXN=100+2;const int MAXM=1000+2;struct Edge{ int u,v,w; friend bool operator<(Edge x,Edge y){ return x.w<y.w;}}e[MAXM],t[MAXM];int N,M,f[MAXN],C=1,Ans,S;int Find(int x){ return x==f[x]?x:Find(f[x]);}void DFS(int x,int l,int w){ if(l==t[x].v+1){ if(w==t[x].w) S++; return; } int a=Find(e[l].u),b=Find(e[l].v); if(a!=b) f[a]=b,DFS(x,l+1,w+1),f[a]=a,f[b]=b; DFS(x,l+1,w);}int main(){ cin >> N >> M; for(int i=1;i<=M;i++) scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w); sort(e+1,e+M+1); for(int i=1;i<=N;i++) f[i]=i; for(int i=1;i<=M;i++){ if(e[i].w!=e[i-1].w) t[C].v=i-1,t[++C].u=i; int a=Find(e[i].u),b=Find(e[i].v); if(a!=b) f[a]=b,t[C].w++,Ans++; } t[C].v=M; if(Ans<N-1){ cout << 0 << endl; return 0; } Ans=1; for(int i=1;i<=N;i++) f[i]=i; for(int i=1;i<=C;i++){ S=0,DFS(i,t[i].u,0),Ans=Ans*S%Mod; for(int j=t[i].u;j<=t[i].v;j++){ int a=Find(e[j].u),b=Find(e[j].v); if(a!=b) f[a]=b; } } cout << Ans << endl; return 0;}
BZOJ1016 JSOI2008 最小生成树计数 生成树+DFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。