程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ 題目1659 Frogs' Neighborhood(度數還原無向圖)

POJ 題目1659 Frogs' Neighborhood(度數還原無向圖)

編輯:關於C++
Frogs' Neighborhood Time Limit: 5000MS   Memory Limit: 10000K Total Submissions: 8348   Accepted: 3538   Special Judge

Description

未名湖附近共有N個大小湖泊L1, L2, ..., Ln(其中包括未名湖),每個湖泊Li裡住著一只青蛙Fi(1 ≤ iN)。如果湖泊LiLj之間有水路相連,則青蛙FiFj互稱為鄰居。現在已知每只青蛙的鄰居數目x1, x2, ..., xn,請你給出每兩個湖泊之間的相連關系。

Input

第一行是測試數據的組數T(0 ≤ T ≤ 20)。每組數據包括兩行,第一行是整數N(2 < N < 10),第二行是N個整數,x1, x2,..., xn(0 ≤ xiN)。

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

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved