USACO3.31Riding the Fences（输出欧拉路径）

都忘了欧拉路径是什么了。。

用dfs搜标记边刚开始直接从I-N搜直接超时 2了先找符合起点和终点的点搜即度数是奇数

d单dfs也超了后来换了个姿势。。

 1 /*
 2     ID: shangca2
 3     LANG: C++
 4     TASK: fence
 5  */
 6 #include <iostream>
 7 #include<cstdio>
 8 #include<cstring>
 9 #include<algorithm>
10 #include<stdlib.h>
11 using namespace std;
12 int w[510][510],n,p[2010],flag,m,de[510],t;
13 void dfs(int u,int d)
14 {
15     for(int v = 1; v <= m ; v++)
16     {
17         if(w[u][v])
18         {
19             w[u][v]--;
20             w[v][u]--;
21             dfs(v,d+1);
22         }
23     }
24     p[t++] = u;
25     return ;
26 }
27 int main()
28 {
29     freopen("fence.in","r",stdin);
30     freopen("fence.out","w",stdout);
31     int i,u,v,st;
32     cin>>n;
33     m = 0;
34     for(i= 1; i <= n ; i++)
35     {
36         scanf("%d%d",&u,&v);
37         m = max(m,max(u,v));
38         de[u]++;
39         de[v]++;
40         w[u][v]++;
41         w[v][u]++;
42     }
43     int f = 1;
44     for(i = 1; i <= m ; i++)
45     {
46         if(de[i]%2!=0)
47         {
48             st = i;
49             break;
50         }
51         if(f&&de[i])
52         {
53             f = 0;
54             st = i;
55         }
56     }
57     dfs(st,1);
58     for(i = t-1; i >= 0 ; i--)
59     printf("%d
",p[i]);
60     return 0;
61 }

View Code