【bzoj1016】[JSOI2008]最小生成树计数

2015.04.21 11:26 Tue | 2次阅读 | 旧日oi | 固定链接 | 源码

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

题解

这题看起来很高级,但是其实就是暴力而已。。
当然纯暴力是不行的,5WA1T……
我们先求出来任意一个最小生成树,并记录每种权值的边在树中出现多少次,记为num[i]。
然后我们证明,每颗最小生成树中,都会用这些条数的边,同时连接这些边后,图的连通性是完全一样的
按从小到大对权值排序
数学归纳法,假设前k-1种权值的边已经连好,考虑第k种权值的边,首先可以肯定,一定不会选多于num[k],否则一定会形成环
如果少于num[i],设少的边为e1,则e1两端的联通块的联通代价变大,就不再是最小生成树了。
然后我们证明任意一种合法的选法得到这num[k]条边加入之后,图的连通性完全一样。
我们发现,如果两种方案选出的边的集合不同,那么不同的边一定相对应的在一个环内,也就是说,只有第k种权值的边构成环的时候,才会出现不同的方案,而在环上,任意删掉一条边,连通性都不变。如果不在环内,那么我们为什么不把这两条边都连上呢?再说它不可能不在,因为之前求最小生成树的时候已经保证了这一点。
于是我们求出每种权值的边的选择方案数,乘法原理乘起来就行了。

我的程序

#include <bits/stdc++.h>
#define ll long long
#define mod 31011
using namespace std;
int n,m,ans=1,sum,cnt;
int fa[105];
struct edge
{
    int u,v;
    ll w;
}e[1005];
struct node{
    int l,r,num;
}a[1005];
bool cmp(const edge &a,const edge &b)
{return a.w<b.w;}
int find(int x)
{return fa[x]==x?x:find(fa[x]);}
int find2(int x)
{return fa[x]==x?x:(fa[x]=find(fa[x]));}
void dfs(int now,int end,int tot)
{
    if(now>end)
    {
        if(!tot) sum++;
        return;
    }
    int p=find(e[now].u),q=find(e[now].v);
    if(p!=q)
    {
        fa[p]=q;
        dfs(now+1,end,tot-1);
        fa[p]=p;
    }
    dfs(now+1,end,tot);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+m+1,cmp);
    int tot=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(e[i].w!=e[i-1].w) a[cnt].r=i-1,a[++cnt].l=i;
        int p=find2(e[i].u),q=find2(e[i].v);
        if(p==q) continue;
        fa[p]=q;tot++;a[cnt].num++;
    }
    a[cnt].r=m;
    if(tot<n-1)
    {
        puts("0");
        return 0;
    }
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=cnt;i++)
    {
        dfs(a[i].l,a[i].r,a[i].num);
        for(int j=a[i].l;j<=a[i].r;j++)
        {
            int p=find(e[j].u),q=find(e[j].v);
            if(p!=q) fa[q]=p;
        }
        ans=ans*sum%mod;
        sum=0;
    }
    cout<<ans<<endl;
    return 0;
}```