POJ 題目1659 Frogs' Neighborhood（度數還原無向圖）

POJ 題目1659 Frogs' Neighborhood（度數還原無向圖）

Description

未名湖附近共有N個大小湖泊L₁, L₂, ..., L_n(其中包括未名湖)，每個湖泊L_i裡住著一只青蛙F_i(1 ≤ i ≤ N)。如果湖泊L_i和L_j之間有水路相連，則青蛙F_i和F_j互稱為鄰居。現在已知每只青蛙的鄰居數目x₁, x₂, ..., x_n，請你給出每兩個湖泊之間的相連關系。

Input

第一行是測試數據的組數T(0 ≤ T ≤ 20)。每組數據包括兩行，第一行是整數N(2 < N < 10)，第二行是N個整數，x₁, x₂,..., x_n(0 ≤ x_i ≤ 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

ac代碼

#include
#include
#include
struct s
{
	int mark,num;
}b[22];
int map[22][22];
int cmp(const void *a,const void *b)
{
	return (*(struct s *)b).num-(*(struct s *)a).num;
}
int main()
{
	int t;
	scanf(%d,&t);
	while(t--)
	{
		int n;
		scanf(%d,&n);
		int i;
		memset(map,0,sizeof(map));
		for(i=0;in-k-1)
				break;
			for(i=1;i<=b[k].num;i++)
			{
				b[k+i].num--;
				if(b[k+i].num<0)
					break;
				map[b[k].mark][b[k+i].mark]=map[b[k+i].mark][b[k].mark]=1;
			}
			if(i<=b[k].num)
				break;
			k++;
		}
		if(k