UVa 10766 Organising the Organisation（矩阵树定理）

72 阅读 0 评论 48 点赞

我是靠谱客的博主欣喜小猫咪，最近开发中收集的这篇文章主要介绍UVa 10766 Organising the Organisation（矩阵树定理），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://vjudge.net/problem/UVA-10766

题意：

给出n, m, k。表示n个点，其中m条边不能直接连通，求生成树个数。

思路：

这也算个裸题，把可以连接的边连接起来，然后矩阵树计算一下即可。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,ll> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn=60+5;
17 
18 int n,m,root;
19 int unable[maxn][maxn];
20 long double C[maxn][maxn];
21 
22 long double Gauss()
23 {
24     for(int k=1; k<=n; k++)  //k表示当前行数，因为行数与列数一样，所以这里k也代表了列数
25     {
26         int max_r=k;
27         for(int i=k+1;i<=n;i++)
28             if(fabs(C[i][k])>fabs(C[max_r][k]))  max_r=i;
29         if(C[max_r][k]==0)  return 0;  //有一列为0,行列式的值必为0
30         if(max_r!=k)
31         {
32             for(int j=k;j<=n;j++)
33                 swap(C[k][j],C[max_r][j]);
34         }
35         for(int i=k+1;i<=n;i++)
36         {
37             long double tmp=C[i][k]/C[k][k];
38             for(int j=k;j<=n;j++)
39                 C[i][j]-=tmp*C[k][j];
40         }
41     }
42     long double ans=1;
43     for(int i=1;i<=n;i++)  ans*=C[i][i];  //化为三角阵后计算主对角线元素乘积
44     ans=fabs(ans);
45     return ans;
46 }
47 
48 int main()
49 {
50     //freopen("in.txt","r",stdin);
51     while(~scanf("%d%d%d",&n,&m,&root))
52     {
53         memset(unable,0,sizeof(unable));
54         memset(C,0,sizeof(C));
55         for(int i=0;i<m;i++)
56         {
57             int u,v;
58             scanf("%d%d",&u,&v);
59             unable[u][v]=unable[v][u]=1;
60         }
61         for(int i=1;i<=n;i++)
62         {
63             for(int j=i+1;j<=n;j++)
64             {
65                 if(!unable[i][j])
66                 {
67                     C[i][i]++; C[j][j]++;
68                     C[i][j]=C[j][i]=-1;
69                 }
70             }
71         }
72         n--;
73         printf("%.0Lfn",Gauss());  //%.Lf codeblocks可能不能正确输出，可以用VS测试
74     }
75     return 0;
76 }