简要题意
现在给出了一个简单无向加权图。你希望知道这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则这两个最小生成树就是不同的）。输出方案数对\(31011\)取模。
SOLUTION
这个题求最小生成树的方案
所以我们从最小生成树入手
（根据kruskal的思路）
我们可以知道 同一个图的每个最小生成树中，边权相等的边数量相等。
感性理解：然后由于要求的是最小生成树的方案所以对于树边，我们只能用同样权值去替代ta
否则就不是最小生成树的值
我们考虑枚举边权
每次根据剩下树边缩点（其实就是将点连上了，方便处理）
得到一张新的DAG，
我们只是要考虑边权相等的边对于新图生成树的方案数
因此我们可以做矩阵树
最后的答案就是所有的乘积
注意：
这个题模数P不是质数
因此不能用逆元求det值
CODE
const int N=1e2+2,M=1e3+2,P=31011;//不是质数
struct node{ll x,y,w;}t[M],s[M];
vector<node> G[M];
bool operator<(node a,node b){
return a.w<b.w;
}
ll is[M],fa[N],c[N],n,D[N][N],A[N][N],C[N][N];
ll find(ll x){
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%P;
a=a*a%P;
b>>=1;
}
return res%P;
}
ll det(ll n){
ll ans=1;
for(ll i=1;i<n;i++){
for(ll j=i+1;j<=n;j++){
while(C[j][i]){
ll l=C[i][i]/C[j][i];//l表示辗转相减的次数
for(ll k=1;k<=n;k++){
C[i][k]=(C[i][k]-C[j][k]*l%P+P)%P;
}
for(ll k=1;k<=n;k++){
swap(C[i][k],C[j][k]);
}//交换两列位置取相反数
ans*=-1;//相反数
}
}
}
for(ll i=1;i<=n;i++){
ans=(ans*C[i][i]%P+P)%P;
}//此时已经削减为上三角矩阵，所以直接求对角线元素之积就可以了
return ans;
}
int main(){
ll n,m,all=0,tmp=0,cnt=0;
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) fa[i]=i;
for(ll i=1;i<=m;i++){
scanf("%lld%lld%lld",&t[i].x,&t[i].y,&t[i].w);
}
sort(t+1,t+m+1);
//kruskal
for(ll i=1;i<=m;i++){
ll x=t[i].x,y=t[i].y,w=t[i].w;
if(w!=tmp) all++,tmp=w;
G[all].push_back(t[i]);
if(find(x)==find(y))continue;
fa[find(x)]=find(y);
is[all]=1;
s[++cnt]=t[i];
s[cnt].w=all;
}
if(cnt!=n-1){
printf("0");
return 0;
}
ll ans=1;
for(ll i=1;i<=all;i++){
if(!is[i]) continue;//如果最小生成树中没有用到此边权
for(ll i=1;i<=n;i++) fa[i]=i;
ll tot=0;
for(ll j=1;j<=cnt;j++){ //将生成树上的边全部连上并缩点
ll x=s[j].x,y=s[j].y,w=s[j].w;
if(w==i) continue;
if(find(x)==find(y))continue;
fa[find(x)]=find(y);
}
for(ll j=1;j<=n;j++){
if(fa[j]==j) c[j]=++tot;
}
for(ll j=1;j<=n;j++){
c[j]=c[find(j)];
}
for(auto j:G[i]){//将原图中此边权的边全部连上
ll x=c[j.x],y=c[j.y];
D[x][x]++,D[y][y]++;
A[x][y]++,A[y][x]++;
}
for(ll j=1;j<=tot;j++){
for(ll k=1;k<=tot;k++){
C[j][k]=(D[j][k]-A[j][k]+P)%P;
}
}
ans=ans*det(tot-1)%P;
for(auto j:G[i]){ //删除连上的边
ll x=c[j.x],y=c[j.y];
D[x][x]--,D[y][y]--;
A[x][y]--,A[y][x]--;
}
}
printf("%lld",ans);
return 0;
}
完结撒花❀