Organising the Organisation UVA - 10766（生成树计数）

题目链接

大意：裸题生成树计数(ps:不是最小生成树）

思路：要用到基尔霍夫矩阵参考博客

代码：也是参考博客的

#include<bits/stdc++.h>
#define maxn 55

using namespace std;

typedef long long ll;

int n,m,k;

ll a[maxn][maxn];
bool maps[maxn][maxn];

ll det(int n){
	ll res=1;
	for(int i=1;i<=n;i++){
		if(!a[i][i]){
			bool flag=true;
			for(int j=i+1;j<=n;j++){
				if(a[j][i]){
					flag=true;
					for(int k=i;k<n;k++){
						swap(a[i][k],a[j][k]);
					}
					res=-res;
					break;
				}
			}
			if(!flag){
				return 0;
			}
		} 
		for(int j=i+1;j<=n;j++){
			while(a[j][i]){
				ll t=a[i][i]/a[j][i];
				for(int k=i;k<=n;k++){
					a[i][k]-=t*a[j][k];
					swap(a[i][k],a[j][k]);
				}
				res=-res;
			}
		}
		res*=a[i][i];
	} 
	return res;
}

int main(){
//	freopen("in.txt","r",stdin);
	while(~scanf("%d%d%d",&n,&m,&k)){
		memset(maps,true,sizeof maps);
		memset(a,0,sizeof a);
		while(m--){
			int i,j;
			scanf("%d%d",&i,&j);
			maps[i][j]=maps[j][i]=false;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(maps[i][j]&&i!=j){
					a[i][i]+=1;
					a[i][j]-=1;
				} 
			}
		}
		printf("%lldn",det(n-1));
	}
	return 0;
} 

最后

以上就是知性老鼠为你收集整理的Organising the Organisation UVA - 10766（生成树计数）的全部内容，希望文章能够帮你解决Organising the Organisation UVA - 10766（生成树计数）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。