【bzoj1016】 JSOI2008—最小生成树计数

http://www.lydsy.com/JudgeOnline/problem.php?id=1016 (题目链接)

题意

　　求图的最小生成树计数。

Solution

　　%了下题解，发现要写矩阵树，150++的程序什么鬼。于是就蒯了hzwer的简便方法。

　　将边按照权值大小排序，将权值相同的边分到一组，统计下每组分别用了多少条边。然后对于每一组进行dfs，判断是否能够用这一组中的其他边达到相同的效果。最后把每一组的方案数相乘就是答案。

　　注意并查集不要压缩路径，不然的话不好回溯。

代码

// bzoj1016

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf 2147483640

#define MOD 31011

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

int getint() {

    int f=1,x=0;char ch=getchar();

    while (ch<='0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}

    while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

const int maxn=1010;

struct edge {int u,v,w;}e[maxn<<2],a[maxn];

int fa[maxn],sum,n,m,cnt,tot;

bool cmp(edge a,edge b) {

    return a.w<b.w;

}

int find(int x) {

    return fa[x]==x ? x : find(fa[x]);

}

void dfs(int x,int now,int k) {

    if (now==a[x].v+1) {

        if (k==a[x].w) sum++;

        return;

    }

    int r1=find(e[now].u),r2=find(e[now].v);

    if (r1!=r2) {

        fa[r1]=r2;

        dfs(x,now+1,k+1);

        fa[r1]=r1,fa[r2]=r2;

    }

    dfs(x,now+1,k);

}

int main() {

    scanf("%d%d",&n,&m);

    for (int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

    for (int i=1;i<=n;i++) fa[i]=i;

    sort(e+1,e+1+m,cmp);

    for (int i=1;i<=m;i++) {

        if (e[i].w!=e[i-1].w) {a[++cnt].u=i;a[cnt-1].v=i-1;}

        int r1=find(e[i].u),r2=find(e[i].v);

        if (r1!=r2) {fa[r1]=r2;a[cnt].w++;tot++;}

    }

    a[cnt].v=m;

    if (tot!=n-1) {printf("0");return 0;}

    for (int i=1;i<=n;i++) fa[i]=i;

    int ans=1;

    for (int i=1;i<=cnt;i++) {

        sum=0;

        dfs(i,a[i].u,0);

        ans=(ans*sum)%MOD;

        for (int j=a[i].u;j<=a[i].v;j++) {

            int r1=find(e[j].u),r2=find(e[j].v);

            if (r1!=r2) fa[r1]=r2;

        }

    }

    printf("%d",ans);

    return 0;

}