[JSOI2008][BZOJ1016] 最小生成树计数

浏览数：16 / 时间：2015年06月09日

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

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 3379 Solved: 1336
[Submit][Status][Discuss]

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,000。数据保证不会出现自回边和重边。注意：具有相同权值的边不会超过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

分析：

首先对边排序，计算出生成树中每种权值对应的边的个数。可以证明，在最小生成树中，每种权值对应的边的个数是相等的，dfs求出每种权值的边的所有组合方案数。最后乘法原理即可。

吐槽：

一开始并查集居然写错了。。唉。。以后还是写三目运算符吧。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,f[101],p,q,sum,ans,tot,cnt;
struct node
{
    int l,r,v;
} edge[1001],a[1001];
bool cmp(node a,node b)
{
    return a.v<b.v;
}
int find(int x)
{
    return x==f[x]?x:find(f[x]);
}    
void dfs(int x,int now,int k)
{
    if (now==a[x].r+1)
    {
        if (k==a[x].v) sum++;
        return;
    }
    int p=find(edge[now].l),q=find(edge[now].r);
    if (p!=q) 
    {
        f[p]=q;
        dfs(x,now+1,k+1);
        f[p]=p;
        f[q]=q;
    }
    dfs(x,now+1,k);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d",&edge[i].l,&edge[i].r,&edge[i].v);
    sort(edge+1,edge+m+1,cmp);
    for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=m;i++)
    {
        if (edge[i].v!=edge[i-1].v) { a[++cnt].l=i; a[cnt-1].r=i-1; }
        p=find(edge[i].l);
        q=find(edge[i].r);
        if (p!=q)
        {
            f[p]=q;
            tot++;
            a[cnt].v++;
        }
    }
    a[cnt].r=m;
    if (tot!=n-1) { printf("0"); return 0; }
    for (int i=1;i<=n;i++) f[i]=i;
    ans=1;
    for (int i=1;i<=cnt;i++)
    {
        sum=0;
        dfs(i,a[i].l,0);
        ans=(ans*sum)%31011;
        for (int j=a[i].l;j<=a[i].r;j++)
        {
            p=find(edge[j].l);
            q=find(edge[j].r);
            if (p!=q) f[p]=q;
        }
    }
    printf("%d",ans);
    return 0;
}