地址：
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;
}