http://acm.pku.edu.cn/JudgeOnline/problem?id=1659
Frogs' Neighborhood
这个题我做的很郁闷方法是对的，但是过样例一直有问题
行久才找出问题，就是在回溯的时候，还原变量的值时没
多想，弄错了，哎，都怪自己太马虎，调了好长时间！
Algorithm: 贪心
怎么谈呢？
具体做法是，每次把点按边的多少排序，然后每次选一个边
最多的点P1，让这个点和其他点P2相连，选取其他点P2的顺序也是
按顺序选，也就是按边的多少。然后一直下去，若最后构造
不出合法的图，就回溯(注意还原变量的值)，调整第二个点P2的选取.
当然有一种情况在读入数据后可以直接判断，就是当所有的边数
之后为奇数时，不能构成图.
代码：
Source Code
| Problem: 1659 |
|
User: lovecanon |
| Memory: 248K |
|
Time: 0MS |
| Language: C++ |
|
Result: Accepted |
#include<iostream>
using namespace std;
struct node{
int id;
int edge;
}Edge[11];
int map[11][11],n;
int cmp(const void *a,const void *b){
struct node *s=(node *)a;
struct node *t=(node *)b;
return t->edge-s->edge;
}
int solve(){
qsort(Edge+1,n,sizeof(Edge[0]),cmp);
if(Edge[1].edge==0) return 1;
else{
int i,j,u,v;
for(i=2;i<=n;i++)
if(map[Edge[1].id][Edge[i].id]==0&&Edge[i].edge!=0){
map[Edge[1].id][Edge[i].id]=1;map[Edge[i].id][Edge[1].id]=1;
Edge[1].edge--;Edge[i].edge--;
u=Edge[1].id;v=Edge[i].id;
if(solve()) return 1;
else{
for(j=1;j<=n;j++) {
if(Edge[j].id==u) Edge[j].edge++;
else if(Edge[j].id==v) Edge[j].edge++;
}
map[u][v]=0;map[v][u]=0;
qsort(Edge+1,n,sizeof(Edge[0]),cmp);
}
}
return 0;
}
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int i,j,sum=0;
scanf("%d",&n);
for(i=1;i<=n;i++) {
scanf("%d",&Edge[i].edge);
Edge[i].id=i;
sum+=Edge[i].edge;
}
if(sum%2) {printf("NO\n\n");continue;}
memset(map,0,sizeof(map));
if(!solve()) {printf("NO\n\n");continue;}
cout<<"YES"<<endl;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(map[i][j]==1) printf("1 ");
else printf("0 ");
}
cout<<endl;
}
cout<<endl;
}
return 0;
}