本文主要是介绍uva10720 - Graph Construction(Havel-Hakimi定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：uva10720 - Graph Construction(Havel-Hakimi定理）
题目大意：给出N个点，并且给出每个点的度，问能否形成简单图。
解题思路：一开始自己写想了些形成简单图的条件，例如度数之和是偶数，度数的一半也就是简单图的边不能超过n * （n - 1） / 2，每个顶点的度数都应该小于总的顶点个数，但后面发现这些只是必要的条件。后来看了题解发现大神们都是用Havel-Hakimi定理。
定理大致内容就是每次都将度数最大的点拿出来，然后分别和每个顶点形成一条边，这样这个点的度为0，然后后面的m（这个顶点的度）个点度都要减1。这样这个点就可以不用在考虑了，然后类似的处理后面的点。如果中间有出现度数为负的就说明形成不了简单图。最后所有的点的度都为0就说明可以。
代码：
#include <stdio.h>
#include <algorithm>
#include <functional>
using namespace std;const int N = 10005;
int vec[N], n;int solve () {//Havel-Hakimi定理for (int i = 0; i < n; i++) {sort (vec + i, vec + n, greater<int>());if (vec[i] > n - i - 1)return 0;for (int j = i + 1; j < i + 1 + vec[i]; j++) {vec[j]--;if (vec[j] < 0)return 0;}vec[i] = 0;}return 1;
}int main () {while (scanf ("%d", &n), n) {for (int i = 0; i < n; i++) scanf ("%d", &vec[i]);printf ("%s\n", solve() ? "Possible": "Not possible");}return 0;
}这篇关于uva10720 - Graph Construction(Havel-Hakimi定理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
