Frogs' Neighborhood
Time Limit: 5000MS Memory Limit: 10000K
Total Submissions: 6076 Accepted: 2636 Special Judge
Description
未名湖附近共有N個大小湖泊L1, L2, ..., Ln(其中包括未名湖)，每個湖泊Li裡住著一只青蛙Fi(1 ≤i ≤ N)。如果湖泊Li和Lj之間有水路相連，則青蛙Fi和Fj互稱為鄰居。現在已知每只青蛙的鄰居數目x1,x2, ..., xn，請你給出每兩個湖泊之間的相連關系。
Input
第一行是測試數據的組數T(0 ≤ T ≤ 20)。每組數據包括兩行，第一行是整數N(2 < N < 10)，第二行是N個整數，x1,x2,..., xn(0 ≤ xi ≤ N)。
Output
對輸入的每組測試數據，如果不存在可能的相連關系，輸出"NO"。否則輸出"YES"，並用N×N的矩陣表示湖泊間的相鄰關系，即如果湖泊i與湖泊j之間有水路相連，則第i行的第j個數字為1，否則為0。每兩個數字之間輸出一個空格。如果存在多種可能，只需給出一種符合條件的情形。相鄰兩組測試數據之間輸出一個空行。
Sample Input
3
7
4 3 1 5 4 2 1
6
4 3 1 4 2 0
6
2 3 1 1 2 1
Sample Output
YES
0 1 0 1 1 0 1
1 0 0 1 1 0 0
0 0 0 1 0 0 0
1 1 1 0 1 1 0
1 1 0 1 0 1 0
0 0 0 1 1 0 0
1 0 0 0 0 0 0
NO
YES
0 1 0 0 1 0
1 0 0 1 1 0
0 0 0 0 0 1
0 1 0 0 0 0
1 1 0 0 0 0
0 0 1 0 0 0
Source
POJ Monthly--2004.05.15 Alcyone@pku
題意：
告訴每只青蛙有幾個鄰居(兩只青蛙若生活在有水路相連的湖泊中則是鄰居)，用矩陣輸出
湖泊的相連關系。
分析：
就是已知每個點的度數，判斷是否可圖。
第一想法是先把鄰居多的安排好（貪心），開始沒想到圖論中的havel定理，只想到先要排序，然後
找到鄰居的相應減1，然後直到所有的青蛙都找到鄰居就結束這種操作。
havel定理：
給定一個非負整數序列{dn}，若存在一個無向圖使得圖中各點的度與此序列一一對應，則稱此序列可圖化。
進一步，若圖為簡單圖，則稱此序列可簡單圖化。
1、Havel-Hakimi定理主要用來判定一個給定的序列是否是可圖的。
2、度序列：若把圖 G 所有頂點的度數排成一個序列 S，則稱 S 為圖 G 的度序列。
3、一個非負整數組成的有限序列如果是某個無向圖的序列，則稱該序列是可圖的。
4、判定過程：（1）對當前數列排序，使其呈遞減，（2）從S【2】開始對其後S【1】個數字-1，（3）
一直循環直到當前序列出現負數（即不是可圖的情況）或者當前序列全為0 （可圖）時退出。
5、舉例：序列S：7,7,4,3,3,3,2,1 刪除序列S的首項 7 ，對其後的7項每項減1，得到：6,3,2,2,2,1,0，
繼續刪除序列的首項6，對其後的6項每項減1，得到：2,1,1,1,0，-1，到這一步出現了負數，因此
該序列是不可圖的。
havel定理的應用：
對於一個給定的度序列，看能不能形成一個簡單無向圖。
Havel算法的思想簡單的說如下：
(1)對序列從大到小進行排序。
(2)設最大的度數為t,把最大的度數置0,然後把最大度數後(不包括自己)的t個度數分別減1(意思就是
把度數最大的點與後幾個點進行連接)
(3)如果序列中出現了負數,證明無法構成。如果序列全部變為0,證明能構成,跳出循環.前兩點不出現，
就跳回第一步！
感想：
看到越來越多轉化為圖連邊來分析問題的做法，好奇妙啊好奇妙~
代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int f[12][12];
struct node
{
int degree,flag;
}a[12];
bool cmp(node x,node y)
{
return x.degree>y.degree;
}
int main()
{
int T,i,j,n;
scanf("%d",&T);
while(T--)
{
memset(f,0,sizeof(f));
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i].degree);
a[i].flag=i;
}
bool succ=1;
while(1)
{
sort(a+1,a+n+1,cmp);
if(a[1].degree==0)
break;
for(i=2;i<=a[1].degree+1;i++)
{
a[i].degree--;
f[a[1].flag][a[i].flag]=1;
f[a[i].flag][a[1].flag]=1;
if(a[i].degree<0)
{
succ=0;
break;
}
}
if(!succ) break;
a[1].degree=0;
}
if(!succ) puts("NO\n");
else
{
puts("YES");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("%d%c",f[i][j],j==n?'\n':' ');
}
puts("");
}
}
return 0;
}
