Bzoj1016 [jsoi2008]最小生成树计数

Posted by yjjr's blog on February 6, 2018

标签:最小生成树Kruskal

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

 

题意:给出一张图,求这张图不同的最小生成树个数

分析:Kruskal求最小生成树时间复杂度为O(n^2),这题可以跑两次最小生成树,第一次算出最终的结果,并且记录相同边权中起同样作用的边数量,第二次dfs回溯用乘法原理计算答案

 

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
    LL 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=1006,mod=31011;
struct edge{int x,y,v;}e[maxn];
struct node{int l,r,v;}a[maxn];
int n,m,cnt,tot,ans=1,sum,fa[106]; 
inline bool cmp(edge a,edge b){return a.v<b.v;}
inline int find(int x){return x==fa[x]?x:find(fa[x]);}
void dfs(int x,int now,int k)//寻找相同边权中符合最小生成树的边数量 
{
	if(now==a[x].r+1){
		if(k==a[x].v)sum++;
		return;
	}
	int r1=find(e[now].x),r2=find(e[now].y);
	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()
{
	n=read(),m=read();
	rep(i,1,n)fa[i]=i;
	rep(i,1,m)e[i]=(edge){read(),read(),read()};
	sort(e+1,e+1+m,cmp);//kruskal按边权大小排序 
	rep(i,1,m){
		if(e[i].v!=e[i-1].v)a[++cnt].l=i,a[cnt-1].r=i-1;//统计不同边权的边个数(左边界和右边界) 
		int r1=find(e[i].x),r2=find(e[i].y);
		if(r1!=r2){fa[r1]=r2;a[cnt].v++;tot++;}
	}
	a[cnt].r=m;
	if(tot!=n-1){printf("0");return 0;}
	rep(i,1,n)fa[i]=i;
	rep(i,1,cnt){
		sum=0;
		dfs(i,a[i].l,0);
		ans=(ans*sum)%mod;
		rep(j,a[i].l,a[i].r){
			int r1=find(e[j].x),r2=find(e[j].y);
			if(r1!=r2)fa[r1]=r2;
		}
	}
	cout<<ans<<endl;
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr