题意
(t)组数据,给出(n)个点的度数,问是否可以构造出一个简单图
sol
havel–hakimi定理:
- 给定一串有限多个非负整数组成的序列,是否存在一个简单图使得其度数列恰为这个序列。
令(s=(d_1,d_2,dots,d_n))为有限多个非负整数组成的非递增序列。 s可简单图化当且仅当有穷序列(s’=(d_2-1,d_3-1,…,d(d_1+1)-1,d(d_1+2),…,d_n))只含有非负整数且是可简单图化的。
最后判断一下是否都是零就好了
感觉这个算法。。就是个贪心吧。。
当然判断这类问题的可行性还有另外一种方法:erdős–gallai定理
令(s=(d_1,d_2,…,d_n))为有限多个非负整数组成的非递增序列。(s)可简单图化当且仅当这些数字的和为偶数,并且
(sum_{i = 1}^k d_i leqslant k(k – 1) + sum_{i = k + 1}^n min(d_i, k))
对所有(1 leqslant k leqslant n)都成立
不过这个好像没办法输出方案??。。。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define pair pair<int, int> #define mp(x, y) make_pair(x, y) #define fi first #define se second using namespace std; const int maxn = 1e5 + 10, inf = 1e9 + 7; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int t, n, reach[101][101], sum = 0; pair a[maxn]; void init() { memset(reach, 0, sizeof(reach)); sum = 0; } int main() { // freopen("a.in", "r", stdin); t = read(); while(t--) { init(); n = read(); for(int i = 1; i <= n; i++) a[i] = mp(read(), i), sum += a[i].fi; if(sum % 2 != 0) {puts("non"); continue;} bool f = 0; for(int i = 1; i <= n; i++) { sort(a + i, a + n + 1, greater<pair>()); if(a[i].fi <= 0) continue; for(int j = i + 1; j <= i + a[i].fi; j++) a[j].fi -= 1, reach[a[i].se][a[j].se] = 1, reach[a[j].se][a[i].se] = 1; a[i].fi = 0; } for(int i = 1; i <= n; i++) if(a[i].fi != 0) {puts("non"); f = 1; break;} if(f) continue; puts("yes"); for(int i = 1; i <= n; i++, puts("")) for(int j = 1; j <= n; j++) printf("%d ", reach[i][j]); puts(""); } } /* 1 6 4 3 1 4 2 0 */
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/607077.html