Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 7134 Solved: 2931
[Submit][Status][Discuss]
Description
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的
最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生
成树可能很多，所以你只需要输出方案数对31011的模就可以了。
Input
第一行包含两个数，n和m，其中1<=n<=100; 1<=m<=1000; 表示该无向图的节点数和边数。每个节点用1~n的整
数编号。接下来的m行，每行包含两个整数：a, b, c，表示节点a, b之间的边的权值为c，其中1<=c<=1,000,000,0
00。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
Output
输出不同的最小生成树有多少个。你只需要输出数量对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
解题思路
matrix tree定理，就是一张图中生成树的个数为此图的度数矩阵-邻接矩阵得到的矩阵
去掉一行一列之后的行列式的值。
模拟最小生成树 克鲁斯卡尔算法，对于相等的边我们只需要考虑每条边对于答案的贡献，也就是他可以与哪些边相连，然后可以看成一堆权值相等的边相连的生成树个数。
行列式用高斯消元可求，代码较为复杂。
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1005;
const double eps = 1e-7;
const int mod = 31011;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
return x*f;
}
int n,m,gg,is[MAXN];
int head[MAXN],cnt,wtf;
int fa[MAXN],sum[MAXN];
int du[MAXN][MAXN];
int a[MAXN][MAXN];
double ans[MAXN][MAXN];
bool used[MAXN];
LL ANS=1;
struct Edge{
int fr,to,v;
}edge[MAXN<<1];
inline void add(int bg,int ed,int w){
edge[++cnt].to=ed;
edge[cnt].fr=bg;
edge[cnt].v=w;
}
inline bool cmp(Edge A,Edge B){
return A.v<B.v;
}
inline int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
inline LL gauss(int n){
double K,s=1.0;
for(register int i=1;i<=n;i++){
if(fabs(ans[i][i])<eps){
LL hv=0;
for(register int j=i+1;j<=n;j++)
if(fabs(ans[j][i])>=eps){
hv=1;
s=-s;
for(register int k=1;k<=n;k++)
swap(ans[i][k],ans[j][k]);
break;
}
if(!hv) return 0;
}
K=1/ans[i][i];
s=s*ans[i][i];
for(register int j=i;j<=n;j++) ans[i][j]=ans[i][j]*K;
for(register int j=i+1;j<=n;j++){
K=ans[j][i];
for(register int k=1;k<=n;k++)
ans[j][k]-=ans[i][k]*K;
}
}
// cout<<s<<endl;
LL ret=(LL)(s+eps+eps);
return ret;
}
int main(){
n=rd();m=rd();
for(register int i=1;i<=m;i++){
int x,y,w;
x=rd();y=rd();w=rd();
add(x,y,w);
}
sort(edge+1,edge+1+cnt,cmp);
for(register int i=1;i<=n;i++) fa[i]=i;
gg=n;
for(register int i=1;i<=m && gg>1;i++){
int u=edge[i].fr;
int v=edge[i].to;
if(find(u)!=find(v)){
used[i]=1;
fa[find(u)]=find(v);
gg--;
}
}
if(gg>1) {
puts("0");
return 0;
}
LL u=1,v=1;
while(v<=m){
for(register int i=1;i<=n;++i){
fa[i]=i;
is[i]=0;
}
for(register int i=1;i<=m;i++){
if(used[i] && edge[i].v!=edge[u].v)
fa[find(edge[i].fr)]=find(edge[i].to);
}
gg=0;
for(register int i=1;i<=n;i++){
if(!is[find(i)])
is[find(i)]=++gg;
is[i]=is[find(i)];
}
for(register int i=1;i<=gg;i++)
for(register int j=1;j<=gg;j++)
ans[i][j]=du[i][j]=a[i][j]=0;
while(edge[u].v==edge[v].v){
du[is[edge[v].fr]][is[edge[v].fr]]++;
du[is[edge[v].to]][is[edge[v].to]]++;
a[is[edge[v].fr]][is[edge[v].to]]++;
a[is[edge[v].to]][is[edge[v].fr]]++;
v++;
}
for(register int i=1;i<=gg;i++)
for(register int j=1;j<=gg;j++)
ans[i][j]=du[i][j]-a[i][j];
// for(register int i=1;i<=n;i++){
// for(register int j=1;j<=n;j++)
// cout<<ans[i][j]<<" ";
// cout<<endl;
// }
--gg;
ANS=ANS*(gauss(gg))%mod;
// cout<<ANS<<endl;
u=v;
}
printf("%lld",ANS);
return 0;
}