地址：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1659
Frogs' Neighborhood
| Time Limit: 5000MS |
|
Memory Limit: 10000K |
| Total Submissions: 1323 |
|
Accepted: 476 |
|
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
貪心：這道題我是每次取最大邊i查找第j個位置是否可以放置，然后不斷更新nei[i],nei[j]。
不過還沒有弄清楚為什么要隨時更新取最大值……請大牛指點……
Source Code
Problem: 1659 User: Headacher
Memory: 396K Time: 0MS
Language: G++ Result: Accepted
Source Code
#include<iostream>
using namespace std;
bool map[11][11];
int nei[11];
int main()
{ int cas,n;
scanf("%d",&cas);
while(cas--)
{ memset(map,0,sizeof(map));
memset(nei,0,sizeof(nei));
scanf("%d",&n);
int i,j,k;
bool flag=0;
int sum=0;
for(i=1;i<=n;i++)
{ scanf("%d",&nei[i]);
sum+=nei[i];
}
sum/=2;
for(i=1;i<=sum;i++)
{
int max=-1;
int v=0;
for(j=1;j<=n;j++)
if(max<nei[j])
{ max=nei[j];
v=j;
}
for(k=1;k<=n;k++)
{ if(nei[v]==0)
break;
if(v!=k&&map[v][k]==0&&nei[k]>0)
{ map[v][k]=1;
map[k][v]=1;
nei[v]--;
nei[k]--;
break;
}
}
}
for(i=1;i<=n;i++)
{ if(nei[i])
{ flag=1;
break;
}
}
if(flag==1)
{ printf("NO\n");
printf("\n");
}
else
{ printf("YES\n");
for(i=1;i<=n;i++)
{ for(j=1;j<n;j++)
printf("%d ",map[i][j]);
printf("%d\n",map[i][j]);
}
printf("\n");
}
}
return 0;
}