Problem Description

現(xiàn)在給出了一個簡單無向加權(quán)圖。你不滿足于求出這個圖的最小生成樹，而希望知道這個圖中有多少個不同的
最小生成樹。（如果兩顆最小生成樹中至少有一條邊不同，則這兩個最小生成樹就是不同的）。由于不同的最小生
成樹可能很多，所以你只需要輸出方案數(shù)對31011的模就可以了。

Input

第一行包含兩個數(shù)，n和m，其中1<=n<=100; 1<=m<=1000; 表示該無向圖的節(jié)點數(shù)和邊數(shù)。每個節(jié)點用1~n的整
數(shù)編號。接下來的m行，每行包含兩個整數(shù)：a, b, c，表示節(jié)點a, b之間的邊的權(quán)值為c，其中1<=c<=1,000,000,0
00。數(shù)據(jù)保證不會出現(xiàn)自回邊和重邊。注意：具有相同權(quán)值的邊不會超過10條。

Output

輸出不同的最小生成樹有多少個。你只需要輸出數(shù)量對31011的模就可以了。

Sample Input

4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1

Sample Output

8

思路：最小生成樹計數(shù)模版題

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 31011; const int N = 1000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;struct Edge {int x,y;int dis;bool operator < (const Edge &rhs) const {return dis<rhs.dis;} } edge[N],tr[N]; int n,m; int father[N]; int G[N][N]; int tot,bel[N],val[N]; int Find(int x) {if(father[x]!=x)return father[x]=Find(father[x]);return x; } int Gauss(int n) {int res=1;for(int i=1; i<=n; i++) {for(int k=i+1; k<=n; k++) {while(G[k][i]) {int d=G[i][i]/G[k][i];for(int j=i; j<=n; j++)G[i][j]=(G[i][j]-1LL*d*G[k][j]%MOD+MOD)%MOD;swap(G[i],G[k]);res=-res;}}res=1LL*res*G[i][i]%MOD,res=(res+MOD)%MOD;}return res; } int Kruskal() {sort(edge+1,edge+m+1);for(int i=1; i<=n; i++)father[i]=i;int cnt=0;for(int i=1; i<=m; i++) {int fu=Find(edge[i].x);int fv=Find(edge[i].y);if(fu==fv)continue;father[fu]=fv,tr[++cnt]=edge[i];if(edge[i].dis!=val[tot])val[++tot]=edge[i].dis;}return cnt; } void addTreeEdge(int v) {for(int i=1; i<n&&tr[i].dis!=v; i++){int x=tr[i].x;int y=tr[i].y;father[Find(x)]=Find(y);}for(int i=n-1; i&&tr[i].dis!=v; i--){int x=tr[i].x;int y=tr[i].y;father[Find(x)]=Find(y);} } void rebuild(int v) {memset(G,0,sizeof(G));for(int i=1; i<=m; i++){if(edge[i].dis==v){int x=bel[edge[i].x];int y=bel[edge[i].y];G[x][y]--;G[y][x]--;G[x][x]++;G[y][y]++;}} } int main() {scanf("%d%d",&n,&m);for(int i=1; i<=m; i++)scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].dis);int cnt=Kruskal();if(cnt!=n-1) {printf("0\n");}else{int res=1;for(int i=1; i<=tot; i++) {for(int i=1; i<=n; i++)father[i]=i;addTreeEdge(val[i]);int blo=0;for(int i=1; i<=n; i++)if(Find(i)==i)bel[i]=++blo;for(int i=1; i<=n; i++)bel[i]=bel[Find(i)];rebuild(val[i]);res=1LL*res*Gauss(blo-1)%MOD;}printf("%d\n",res);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的最小生成树计数（HYSBZ-1016）(加强版实现)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。