【BZOJ 1016】 1016: [JSOI2008]最小生成树计数 （DFS|矩阵树定理）

1016: [JSOI2008]最小生成树计数

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

HINT

Source

【分析】

　　不知道结论是不可以做的吧？表示也不会矩阵树定理。。dfs方法也要知道一些证明才能说明其准确性。

　　【以后的博客都要留坑了？

　　安利两种题解：

　　1、我的打法：（不看都不知道为什么这样做是对的）

　　https://blog.sengxian.com/solutions/bzoj-1016

　　http://www.cnblogs.com/lcf-2000/p/5575412.html

　　2、矩阵树（没打这种，还不会）

　　http://blog.csdn.net/jarily/article/details/8902509

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1100
#define Maxm 10100
#define Mod 31011

struct node
{
    int x,y,c;
}t[Maxm];

bool cmp(node x,node y) {return x.c<y.c;}
int a[Maxm],l[Maxm],r[Maxm],fa[Maxn];

int ffa(int x)
{
     return x==fa[x]?x:ffa(fa[x]);
}

int ct;
void ffind(int x,int nw,int h)
{
    if(nw==r[x]+1)
    {
        if(h==a[x]) ct++;
        return;
    }
    int x1=ffa(t[nw].x),x2=ffa(t[nw].y);
    if(x1!=x2)
    {
        fa[x1]=x2;
        ffind(x,nw+1,h+1);
        fa[x1]=x1;
    }
    ffind(x,nw+1,h);
}

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].c);
    }
    sort(t+1,t+1+m,cmp);
    int cnt=0,tot=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(i==1||t[i].c!=t[i-1].c)
        {
            r[cnt]=i-1;l[++cnt]=i;
            a[cnt]=0;
        }
        int x1=ffa(t[i].x),x2=ffa(t[i].y);
        if(x1!=x2)
        {
            fa[x1]=x2;
            a[cnt]++;
            tot++;
        }
        
    }r[cnt]=m;
    if(tot!=n-1) printf("0
");
    else
    {
        for(int i=1;i<=n;i++) fa[i]=i;
        int ans=1;
        for(int i=1;i<=cnt;i++)
        {
            ct=0;
            ffind(i,l[i],0);
            ct%=Mod;
            ans=ans*ct;ans%=Mod;
            for(int j=l[i];j<=r[i];j++)
            {
                int x1=ffa(t[j].x),x2=ffa(t[j].y);
                if(x1!=x2) fa[x1]=x2;
            }
        }
        printf("%d
",ans);
    }
    return 0;
}

2017-02-28 13:58:04