一道mst……
最开始是毫无头绪,于是就点开了--->题解
大部分题解都是矩阵树……然而第一篇题解告诉了我们暴搜也能过(
思路大概是说,对于一个图\(G\),它的所有最小生成树的相同权值的边的数量是相等的。
(这里批评自己一下(虽然AC了但是最终没有证明这个思路的正确性()
(不过花了一些时间来尝试……最后没能成功举出反例,于是就默认这是对的了()
对边的权值排序,直接跑一遍mst,用结构体来记录相同权值的边出现的次数。然后暴搜一通边就完了qwq
神仙数据
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define mod 31011
#define MAXN 105
#define MAXM 1005
using namespace std;
struct segm
{
int u,v,w;
}e[MAXM];
struct sums
{
int l,r,value;
}a[MAXM];
int n,m,f[MAXN],toti=0,tot=0,sum,ans=1;
int find(int q)
{
if (q==f[q]) return q;
return find(f[q]);
}
bool cmp(segm x,segm y)
{
return x.w<y.w;
}
void dfs(int wei,int cur,int del)
{
if (cur==a[wei].r+1)
{
if (del==a[wei].value)
{
sum++;
}
return;
}
int xx=find(e[cur].u),yy=find(e[cur].v);
if (xx!=yy)
{
f[xx]=yy;
dfs(wei,cur+1,del+1);
f[xx]=xx; f[yy]=yy;
}
dfs(wei,cur+1,del);
return;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
f[i]=i;
}
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
sort(e+1,e+m+1,cmp);
for (int i=1;i<=m;i++)
{
if (e[i].w!=e[i-1].w)
{
a[tot].r=i-1;
a[++tot].l=i;
}
int xx=find(e[i].u),yy=find(e[i].v);
if (xx!=yy)
{
f[xx]=yy;
a[tot].value++;
toti++;
}
}
if (toti!=n-1)
{
printf("0");
return 0;
}
a[tot].r=m;
for (int i=1;i<=n;i++)
{
f[i]=i;
}
for (int i=1;i<=tot;i++)
{
sum=0;
dfs(i,a[i].l,0);
ans=(ans*sum)%mod;
for (int j=a[i].l;j<=a[i].r;j++)
{
int xx=find(e[j].u),yy=find(e[j].v);
if (xx!=yy)
{
f[xx]=yy;
}
}
}
printf("%d",ans);
return 0;
}