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

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

8

 

分析:

首先对边排序,计算出生成树中每种权值对应的边的个数。可以证明,在最小生成树中,每种权值对应的边的个数是相等的,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;
}

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。