UVa 208 - Firetruck

这道题代码很容易写出来，难点在于很容易超时（特别是起点端图特别稠密的情况下，终点与起点没有连接），解决方法是先从终点找连接点。

1 #include <cstdio>
 2 #include <cstring>
 3 int G[25][25];
 4 int vis[25];
 5 int join[22];
 6 int e;
 7 int r=0;
 8 void find_join(int u){
 9     join[u]=1;
10     for(int v=0;v<25;v++){
11         if(!join[v] && G[u][v])
12             find_join(v);
13     }
14 }
15 int dfs(int s,int k,int *a){
16     a[k]=s;
17     if(s==e){
18         for(int i=0;i<k;i++){
19             printf("%d ",a[i]);
20         }
21         r++;
22         if(k>=0)printf("%d",a[k]);
23         printf("\n");
24         return 1;
25     }
26     int ok=0;
27     for(int i=0;i<25;i++){
28         if(G[s][i]&&!vis[i]&&join[i]){
29             vis[i]=1;
30             if(dfs(i,k+1,a))ok=1;
31             vis[i]=0;
32         }
33     }
34     if(ok)return 1;
35     else return 0;
36 }
37 int main(){
38     int cnt = 0;
39     while(scanf("%d",&e)!=EOF){
40         memset(G,0,sizeof(G));
41         memset(join,0,sizeof(join));
42         memset(vis,0,sizeof(vis));
43         int a,b;
44         while(scanf("%d%d",&a,&b)==2&&(a||b)){
45             G[a][b]=1;
46             G[b][a]=1;
47         }
48 
49         int t[25];
50         vis[1]=1;
51         printf("CASE %d:\n",++cnt);
52         r=0;
53         find_join(e);
54         dfs(1,0,t);
55         printf("There are %d routes from the firestation to streetcorner %d.\n",r,e);
56     }
57     return 0;
58 }