都忘了欧拉路径是什么了。。
用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