LOJ #10070 最小生成树计数

佚名 6年前 (2019-04-12) 随笔 1770人围观抢沙发百度已收录

一道mst……

最开始是毫无头绪，于是就点开了--->题解

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

大部分题解都是矩阵树……然而第一篇题解告诉了我们暴搜也能过（

思路大概是说，对于一个图\(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;
}