97北縣賽-4-金幣問題
作法:DFS
搜尋的終止條件很重要
/******************************************************/
#include<stdio.h>
#include<stdlib.h>
int map[256][256]={0},flag[256]={0};
int n,k;
int maptop[256]={0},way[256]={0},x,y,max;
void DFS(int now,int time)
{
int a,find=0;
if(time>max) max=time;
if(now>n||(n-now+1)/2+time+2<=max) return;
for(a=0;a<maptop[now];a++)
if(flag[map[now][a]]==1)
{find=1;break;}
if(find==0)
{
flag[now]=1;
DFS(now+1,time+1);
flag[now]=0;
}
DFS(now+1,time);
}
main()
{
int a,b;
scanf("%d",&n);
for(a=0;a<=n;a++) {maptop[a]=0;flag[a]=0;way[a]=0;}
while(scanf("%d",&x)==1&&x!=0)
{
scanf("%d",&y);
map[x][maptop[x]]=y;
maptop[x]++;
map[y][maptop[y]]=x;
maptop[y]++;
}
max=0;
DFS(1,0);
printf("%d\n",max);
return 0;
}
不太懂這行的意思(n-now+1)/2+time+2<=max
但如果剩下的點沒有連結
不是全部都算?