http://acm.pku.edu.cn/JudgeOnline/problem?id=1659
Frogs' Neighborhood
這個(gè)題我做的很郁悶方法是對(duì)的，但是過樣例一直有問題
行久才找出問題，就是在回溯的時(shí)候，還原變量的值時(shí)沒
多想，弄錯(cuò)了，哎，都怪自己太馬虎，調(diào)了好長(zhǎng)時(shí)間！
Algorithm: 貪心
怎么談呢？
具體做法是，每次把點(diǎn)按邊的多少排序，然后每次選一個(gè)邊
最多的點(diǎn)P1，讓這個(gè)點(diǎn)和其他點(diǎn)P2相連，選取其他點(diǎn)P2的順序也是
按順序選，也就是按邊的多少。然后一直下去，若最后構(gòu)造
不出合法的圖，就回溯(注意還原變量的值)，調(diào)整第二個(gè)點(diǎn)P2的選取.
當(dāng)然有一種情況在讀入數(shù)據(jù)后可以直接判斷，就是當(dāng)所有的邊數(shù)
之后為奇數(shù)時(shí)，不能構(gòu)成圖.
代碼：
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;
}