Frogs' Neighborhood（POJ1659+Havel-Hakimi定理）

题目：

题意：根据他给你的每个点的度数构造一张无向图。

思路：自己WA了几发（好菜啊……）后看到discuss才知道这个要用Havel-Hakimi定理，就跑去搜，这个定理很好理解，想了解的看官请点击链接：http://blog.51cto.com/sbp810050504/883904。

代码实现如下：

 1 #include <set>
 2 #include <map>
 3 #include <queue>
 4 #include <stack>
 5 #include <cmath>
 6 #include <bitset>
 7 #include <cstdio>
 8 #include <string>
 9 #include <vector>
10 #include <cstdlib>
11 #include <cstring>
12 #include <iostream>
13 #include <algorithm>
14 using namespace std;
15 
16 typedef long long ll;
17 typedef pair<ll, ll> pll;
18 typedef pair<ll, int> pli;
19 typedef pair<int, ll> pil;;
20 typedef pair<int, int> pii;
21 typedef unsigned long long ull;
22 
23 #define lson i<<1
24 #define rson i<<1|1
25 #define bug printf("*********
");
26 #define FIN freopen("D://code//in.txt", "r", stdin);
27 #define debug(x) cout<<"["<<x<<"]" <<endl;
28 #define IO ios::sync_with_stdio(false),cin.tie(0);
29 
30 const double eps = 1e-8;
31 const int mod = 10007;
32 const int maxn = 1e6 + 7;
33 const double pi = acos(-1);
34 const int inf = 0x3f3f3f3f;
35 const ll INF = 0x3f3f3f3f3f3f3f;
36 
37 int t, n;
38 int mp[15][15];
39 
40 struct node {
41     int id, w;
42     bool operator < (const node& x) const {
43         return w > x.w;
44     }
45 }a[15];
46 
47 int main() {
48     //FIN;
49     scanf("%d", &t);
50     for(int icase = 1; icase <= t; icase++) {
51         if(icase != 1) printf("
");
52         memset(mp, 0, sizeof(mp));
53         scanf("%d", &n);
54         for(int i = 1; i <= n; i++) {
55             scanf("%d", &a[i].w);
56             a[i].id = i;
57         }
58         int flag = 1;
59         for(int i = 1; i <= n; i++) {
60             sort(a + 1, a + n + 1);
61             for(int j = 1; j <= a[1].w; j++) {
62                 a[j+1].w--;
63                 mp[a[1].id][a[j+1].id] = mp[a[j+1].id][a[1].id] = 1;
64             }
65             a[1].w = 0;
66             for(int j = 1; j <= n; j++) {
67                 if(a[j].w < 0) {
68                     flag = 0;
69                     break;
70                 }
71             }
72             if(!flag) break;
73         }
74         if(!flag) puts("NO");
75         else {
76             puts("YES");
77             for(int i = 1; i <= n; i++) {
78                 for(int j = 1; j <= n; j++) {
79                     printf("%d%c", mp[i][j], j == n ? '
' : ' ');
80                 }
81             }
82         }
83     }
84     return 0;
85 }