10720 Graph Construction(Havel-Hakimi定理 )

有个细节没注意,wa了好多遍,运用 Havel-Hakimi定理  可解

Havel-Hakimi定理讲解 http://sbp810050504.blog.51cto.com/2799422/883904

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int N = 10000+10;
int num[N], n;
int cmp(int a, int b)
{return a > b;
}
int main(void)
{while(scanf("%d", &n) && n){for(int i = 0;i < n;i++)scanf("%d", &num[i]);int ok = 1;for(int i = 0;i < n-1;i++){sort(num+i, num+n, cmp);if(i + num[i] >= n || ok == 0){ok = 0;break;}for(int j = i+1;j < i+num[i]+1;++j){num[j]--;if(num[j] < 0){ok = 0;break;}}}if(num[n-1] != 0)ok = 0;if(ok)puts("Possible");elseputs("Not possible");}return 0;
}