[LuoguP4208][JSOI2008]最小生成树计数
题面
现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方案数对31011的模就可以了。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过10条。
分析
引理:同一个图的所有最小生成树中，边权相等的边数量相等
考虑Kruskal算法的过程,我们会按边权依次加入两端点不属于同一连通块的边。边权相同的边是连续加入的，因此操作等价于加入所有边权相同的边,然后消除所有简单环,不同的消环方式对应不同的生成树。消除一个简单环等价于删掉环中一条边。所以,无论怎么消环,最后剩余的总边数一定。
根据这个引理,我们可以求出每一种边权的选择方案，再乘起来得到答案。对于每种边权,我们将最小生成树上非该边权的边加到一个新图上,然后把每个连通块缩成一个点。之后将原图上所有边权为该值的边都加在新图上。新图的生成树个数即为答案,用Matrix-Tree定理求解。(其实这里的生成树个数和引理证明里提到的消环方案数是等价的)
可以证明复杂度为\(\Theta(n^3)\)
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100
#define maxm 1000
#define mod 31011
using namespace std;
typedef long long ll;
int n,m;
struct DSU{
int fa[maxn+5];
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
void merge(int x,int y){
fa[find(x)]=find(y);
}
void ini(int n){
for(int i=1;i<=n;i++) fa[i]=i;
}
};
struct edge{
int from;
int to;
int len;
bool on_tree;
friend bool operator < (edge p,edge q){
return p.len<q.len;
}
}G[maxm+5];
int cnt=0;
int tlen[maxn+5];//因为不同MST中边权相等的边数量相等,按边权给边分类
void kruskal(){
static DSU S;
S.ini(n);
sort(G+1,G+1+m);
for(int i=1;i<=m;i++){
int x=G[i].from,y=G[i].to;
if(S.find(x)!=S.find(y)){
S.merge(x,y);
G[i].on_tree=1;
tlen[++cnt]=G[i].len;
}
}
sort(tlen+1,tlen+1+cnt);
cnt=unique(tlen+1,tlen+1+cnt)-tlen-1;
}
ll g[maxn+5][maxn+5];
void add_edge(int u,int v){
g[u][u]=(g[u][u]+1)%mod;
g[u][v]=(g[u][v]-1)%mod;
g[v][v]=(g[v][v]+1)%mod;
g[v][u]=(g[v][u]-1)%mod;
}
ll gauss(int n){
ll ans=1;
for(int i=1;i<n;i++){
for(int j=i+1;j<n;j++){
while(g[j][i]){
int d=g[i][i]/g[j][i];
for(int k=1;k<n;k++) g[i][k]=(g[i][k]-g[j][k]*d%mod+mod)%mod;
for(int k=1;k<n;k++) swap(g[i][k],g[j][k]);
ans=mod-ans;
}
}
if(g[i][i]==0) return 0;
ans=ans*g[i][i]%mod;
}
return (ans%mod+mod)%mod;
}
ll calc(int len){
static int bel[maxn+5];
static DSU S;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=0;
S.ini(n);
for(int i=1;i<=m;i++){//把最小生成树上不等于len的边构成的连通块缩点
if(G[i].len!=len&&G[i].on_tree) S.merge(G[i].from,G[i].to);
}
int ptr=0;
for(int i=1;i<=n;i++) if(S.find(i)==i) bel[i]=++ptr;
for(int i=1;i<=n;i++) bel[i]=bel[S.find(i)];//要重标号再求生成树
for(int i=1;i<=m;i++){//对等于len的边构成的新图求生成树数量
if(G[i].len==len) add_edge(bel[G[i].from],bel[G[i].to]);
}
return gauss(ptr);
}
int main(){
// int u,v,w;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d %d %d",&G[i].from,&G[i].to,&G[i].len);
kruskal();
ll ans=1;
for(int i=1;i<=cnt;i++){
ans=ans*calc(tlen[i])%mod;
}
printf("%lld\n",ans);
}