Havel定理判定简单图
被上下界网络流烦傻了，暂时不想写代码太长的题。
虽然是一道水题，但也是建立在一定理论基础上的。
再科普一下简单图，没有重边没有自环的图就是简单图。区别有向图和无向图，也就是说，有向图的反向边不算重边。
给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化
可图化的判定：
( \sum_{i=1}^{n}d_{i} mod 2 == 0 ) 。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。
可简单图化的判定（Havel定理）：
把序列排成不增序，即 ( d_1 \geq d_2 \geq \ldots \geq d_n )，则d可简单图化当且仅当
( d’ = \left{ d_2-1 , d_3-1 \ldots d_{d_1+1}-1 , d_{d_1+2} , d_{d_1+3} , \ldots d_n \right} ) 可简单图化。简单的说，把d排序后，找出度最大的点（ 设度为( d_1) ），把它与度次大的d1个点之间连边，然后这个点就可以不管了，一直继续这个过程，直到建出完整的图，或出现负度等明显不合理的情况。
题意：
题目很长……没怎么看，就是给你几个点，再给你每个点的度数，问你能否构成简单图。
思路：
裸题，按照定理模拟一下即可。
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1005;
int deg[maxn];
int main()
{
int T, n;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
bool flag = true;
int sum = 0;
for (int i = 0; i < n; i++) {
scanf("%d", deg + i);
sum += deg[i];
if (deg[i] >= n)
flag = false;
}
if (sum & 1)
flag = false;
if (!flag) {
puts("no");
continue;
}
for (int i = 0; i < n; i++) {
sort(deg + i, deg + n, greater<int>());
int d = deg[i];
if (d < 0 || i + d >= n) {
flag = false;
break;
}
for (int j = 1; j <= d; j++)
deg[i + j]--;
}
puts(flag ? "yes" : "no");
}
return 0;
}