我是靠谱客的博主 大胆蚂蚁,这篇文章主要介绍UVA 10766 Organising the Organisation(生成树计数),现在分享给大家,希望可以做个参考。

题目链接:
UVA 10766 Organising the Organisation
题意:
给出 n,m,k ,代表一家公司有 n 个人,编号从1n,且指定编号为 k 的人为总经理,然后有m组关系,表示 a[i] 不想和 b[i] 有领属关系,求领属关系图的种类数?
数据范围:
1n50,1mn,0k1500
分析:
我觉得 k 的范围好像不大对,但是因为这道题实际上和k值无关,所以也就无关紧要了( ? )
把关系图看成一颗生成树,其实把所有可以存在领属关系的点看成可以连边,那么就是求生成树的个数了。
需要知道每个点的度数和点与点能够连边。
我是先默认每个点的度数为n1,默认任意两点可以 ,然后对于每个不能连边的 a,b ,将邻接矩阵 C[a][b]=C[b][a]=0 ,同时 degree[a],degree[b] .但是这道题有重边啊,这样子一来 degree[a],degree[b] 会多减了,所以需要先判断 C[a][b] 是否为 0 ,然后才决定是否degree[a],degree[b]

这道题还要用 longdouble 才能保证精度。。。
输入输出可以使用 cincout

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <climits> #include <cmath> #include <ctime> #include <cassert> #include <iomanip> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; typedef long long ll; const int MAX_N = 110; const double eps = 1e-8; int degree[MAX_N]; long double C[MAX_N][MAX_N]; int sgn(long double x) { if(fabs(x) < eps) return 0; else if(x > 0) return 1; else return -1; } long double det(long double mat[][MAX_N], int n) { long double res = 1.0; int cnt = 0; for(int i = 0; i < n; ++i) { if(sgn(mat[i][i]) == 0) { for(int j = i + 1; j < n; ++j) { if(sgn(mat[j][i] != 0)) { for(int k = i; k < n; ++k) { swap(mat[i][k], mat[j][k]); } cnt++; break; } } } if(sgn(mat[i][i]) == 0) return 0; res *= mat[i][i]; for(int j = i + 1; j < n; ++j) { mat[j][i] /= mat[i][i]; } for(int j = i + 1; j < n; ++j) { for(int k = i + 1; k < n; ++k) { mat[j][k] -= mat[j][i] * mat[i][k]; } } } if(cnt & 1) res = -res; return res; } int main() { int n, m, k; while(cin >> n >> m >> k) { memset(degree, 0, sizeof(degree)); memset(C, 0, sizeof(C)); for(int i = 0; i < n; ++i) { degree[i] = n - 1; //默认每个点的入度为n - 1 for (int j = 0; j < n; ++j) { //先默认任意两点可以建边 C[i][j] = -1; } } for(int i = 0; i < m; ++i) { int a, b; cin >> a >> b; a--, b--; if(sgn(C[a][b]) == 0) continue; //会有重边啊!!! C[a][b] = C[b][a] = 0; //不能建边 degree[a]--, degree[b]--; } for(int i = 0; i < n; ++i) { C[i][i] = degree[i]; } cout << fixed << setprecision(0) << det(C, n - 1) << endl; } return 0; }

最后

以上就是大胆蚂蚁最近收集整理的关于UVA 10766 Organising the Organisation(生成树计数)的全部内容,更多相关UVA内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(98)

评论列表共有 0 条评论

立即
投稿
返回
顶部