http://acm.hdu.edu.cn/showproblem.php?pid=4408

題意：求最小生成樹個數

題解：對于Kruskal算法，我們發現，最小生成樹要想用多種方法就要有長度相同的邊。而且，我們發現，kruskal處理完長度所有為c1的邊之后，他的結果就是用長度為c1的邊生成了一棵樹，而且這棵樹對于下面的影響都是一樣的，因為只有效果重復的邊才不會被加入集合，所以我們只需要記錄每一個階段的生成樹個數然后相乘就可以了。

? 實現起來，在一個階段內，要想有多種方法，必定是有的邊成環了，也就是形成了聯通塊，所以我們只需要找到聯通塊，然后在這些聯通塊內生成樹就可以了。我們用并查集維護縮點。具體細節看注釋。

代碼：

#include <iostream> #include<cstdio> #include<algorithm> #include<vector> #include<cstring> using namespace std; typedef long long ll; const int maxn =105; const int maxm =1005; //生成樹計數模板 ll mode; ll a[maxn][maxn];//生成樹計數模板 ll det(int n){int i,j,k;ll ans=1;for(i=0;i<n;i++)for(j=0;j<n;j++)a[i][j]%=mode;for(i=0;i<n;i++){for(j=i+1;j<n;j++){while(a[j][i]){int tmp=a[i][i]/a[j][i];for(k=i;k<n;k++){a[i][k]=((a[i][k]-tmp*a[j][k])%mode+mode)%mode;swap(a[i][k],a[j][k]);}ans=-ans;}}if(a[i][i]==0)return 0;ans=ans*a[i][i]%mode;}return (ans%mode+mode)%mode; } ///并查集部分 //over_p記錄之前已經更新過的所有的關系，now_p記錄當前這一層的關系 int now_p[maxn],over_p[maxn]; int finde(int x,int p[]){return p[x]==x?x:p[x]=finde(p[x],p); } void join(int x,int y,int p[]){x=finde(x,p);y=finde(y,p);if(x==y)return ;p[x]=y;return ; } //slove struct node{int u,v,w; }e[maxm]; bool cmp(node a,node b){return a.w<b.w; } int n,m; ll ans; int vis[maxn]; vector<int> g[maxn]; void init(){int i;for(i=0;i<n;i++){now_p[i]=i;over_p[i]=i;g[i].clear();}memset(vis,0,sizeof(vis));sort(e,e+m,cmp); } int mp[maxn][maxn]; ll max_mst_num(){if(m==0)return 0;ans=1;int i,j;int x,y;init();int now=e[0].w;for(i=0;i<=m;i++){if(e[i].w==now&&i!=m){//查找被縮成的點x=finde(e[i].u,over_p);y=finde(e[i].v,over_p);if(x==y)continue;//之前被縮為一點join(x,y,now_p);//在一個集合內等待縮點vis[x]=1;vis[y]=1;mp[x][y]++;//鄰接矩陣不再是0，1矩陣，因為這里進行了縮點，要保存這一點所有的關系mp[y][x]++;}else {for(j=0;j<n;j++){if(vis[j]){vis[j]=0;g[finde(j,now_p)].push_back(j);//將一個聯通塊加入一個vector}}for(j=0;j<n;j++){if(g[j].size()>1){int len=g[j].size();memset(a,0,sizeof(a));for(x=0;x<len;x++){for(y=x+1;y<len;y++){int tmp1,tmp2;tmp1=g[j][x];tmp2=g[j][y];a[x][y]=a[y][x]=-mp[tmp1][tmp2];a[x][x]+=mp[tmp1][tmp2];a[y][y]+=mp[tmp1][tmp2];//x,y為點在這一聯通塊內的編號，計算時用這個編號形成的矩陣}}ans=(ans*det(len-1)%mode+mode)%mode;//對這一聯通塊生成樹計數for(x=0;x<len;x++)over_p[g[j][x]]=j;//將這一層的關系記錄到全局關系中}}memset(mp,0,sizeof(mp));//初始化當前關系為下一輪準備for(j=0;j<n;j++){now_p[j]=finde(j,over_p);g[j].clear();}now=e[i].w;if(i>=m)break;i--;}}now=finde(0,over_p);for(i=0;i<n;i++)if(finde(i,over_p)!=now)return 0;return ans; } int main() {int i;//freopen("1.txt","r",stdin);while(cin>>n>>m>>mode){if(n==0&&m==0&&mode==0)break;for(i=0;i<m;i++){scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);e[i].v--;e[i].u--;//別忘了}ll ans=max_mst_num();ans=(ans%mode+mode)%mode;printf("%lld\n",ans);}// cout << "Hello world!" << endl;return 0; }

?

總結

以上是生活随笔為你收集整理的HDU 4408 Minimum Spanning Tree 最小生成树计数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。