https://www.lydsy.com/JudgeOnline/problem.php?id=1016
現在給出了一個簡單無向加權圖。你不滿足于求出這個圖的最小生成樹，而希望知道這個圖中有多少個不同的最小生成樹。（如果兩顆最小生成樹中至少有一條邊不同，則這兩個最小生成樹就是不同的）。由于不同的最小生成樹可能很多，所以你只需要輸出方案數對31011的模就可以了。
無外乎兩種：K算法和P算法（當然還有第三種但是我不會（滑稽）
P算法沒法解于是用K算法。
發現K算法的正確性后其實我們需要做的工作就是從K算法找到一些邊，可以用另一些邊權一樣的邊替換并且是一棵生成樹即可。
于是我們枚舉即可。
（當然你會有兩個問題：1.為什么邊權一樣即可替換，2.前面的邊的操作對后面邊是否有影響？）
（所以暴力選手不過腦子的話就很輕松的敲完代碼走人了（比如我））
（實際為兩個定理，分別為：
1.不同的最小生成樹中,每種權值的邊出現的個數是確定的。
2.不同的生成樹中,某一種權值的邊連接完成后,形成的聯通塊狀態是一樣的 。
百度一下。）
（https://blog.csdn.net/jarily/article/details/8902402可能這個解釋靠譜些？）
#include<algorithm> #include<iostream> #include<cstring> #include<cctype> #include<cstdio> #include<vector> #include<cmath> using namespace std; typedef long long ll; const int N=101; const int M=1010; const int p=31011; inline int read(){int X=0,w=0;char ch=0;while(!isdigit(ch)){w|=ch=='-';ch=getchar();}while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } struct node{int u,v,w; }e[M]; struct range{int l,r; }a[M]; int fa[N],t[M],n,m,k,sum; inline bool cmp(node a,node b){return a.w<b.w; } int find(int x){if(fa[x]==x)return x;return find(fa[x]); } inline void unionn(int x,int y){fa[x]=y; } inline void destory(int x,int y){fa[x]=x;fa[y]=y; } void dfs(int l,int r,int d,int w){if(l>r){if(d==t[w])sum=(sum+1)%p;return;}if(r-l+1+d<t[w])return;int u=find(e[l].u),v=find(e[l].v);if(u!=v&&d<t[w]){unionn(u,v);dfs(l+1,r,d+1,w);destory(u,v); }dfs(l+1,r,d,w); } int main(){n=read(),m=read();for(int i=1;i<=m;i++){e[i].u=read(),e[i].v=read(),e[i].w=read();}sort(e+1,e+m+1,cmp);for(int i=1;i<=n;i++)fa[i]=i;int cnt=0;for(int i=1;i<=m;i++){if(e[i].w!=e[i-1].w){a[++k].l=i;a[k-1].r=i-1;}int u=e[i].u,v=e[i].v;u=find(u),v=find(v);if(u!=v)t[k]++,cnt++,unionn(u,v);}a[k].r=m;if(cnt!=n-1){puts("0");return 0;}int ans=1;for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=k;i++){if(!t[i])continue;sum=0;dfs(a[i].l,a[i].r,0,i);ans=(ll)ans*sum%p;for(int j=a[i].l;j<=a[i].r;j++){int u=e[j].u,v=e[j].v;u=find(u),v=find(v);if(u!=v)unionn(u,v);}}printf("%d\n",ans);return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+歡迎訪問我的博客：http://www.cnblogs.com/luyouqi233/?+
+++++++++++++++++++++++++++++++++++++++++++
)
)
