午夜的留言附属站 » 日志 » fence, Eulerian Tours problem
fence, Eulerian Tours problem
任腾 发表于 2007-08-08 06:36:50
1. /*
2. TASK:fence
3. LANG:JAVA
4. ID:tobais1
5. */
6.
7. import java.io.*;
8. import java.util.*;
9.
10. class fence{
11. static int[] stack=new int[501],d=new int[1300];
12. static int n=0,m,dn=0;
13. static int[][] a=new int[501][501];
14.
15. static void solve(int now){
16. for (int i=1;i<=n;i++){
17. if (a[now][i]>0){
18. a[now][i]--;
19. a[i][now]--;
20. solve(i);
21. }
22. }
23. d[dn++]=now;
24. }
25. public static void main(String[] args)throws IOException{
26. Scanner fin=new Scanner(new File("fence.in"));
27. PrintWriter fout=new PrintWriter(new File("fence.out"));
28. int[] dd=new int[501];
29. m=fin.nextInt();
30. int minv=10000;
31. for (int i=0;i<m;i++){
32. int x=fin.nextInt(),y=fin.nextInt();
33. a[x][y]++;
34. a[y][x]++;
35. dd[x]++;dd[y]++;
36. if (x<minv) minv=x;
37. if (y<minv) minv=y;
38. if (x>n) n=x;
39. if (y>n) n=y;
40. }
41. for (int i=1;i<=n;i++)
42. if (dd[i]%2==1) {solve(i);break;}
43. if (dn==0) solve(minv);
44. for (int i=dn-1;i>=0;i--) fout.println(d[i]);
45. fout.close();
46. }
47. }
2. TASK:fence
3. LANG:JAVA
4. ID:tobais1
5. */
6.
7. import java.io.*;
8. import java.util.*;
9.
10. class fence{
11. static int[] stack=new int[501],d=new int[1300];
12. static int n=0,m,dn=0;
13. static int[][] a=new int[501][501];
14.
15. static void solve(int now){
16. for (int i=1;i<=n;i++){
17. if (a[now][i]>0){
18. a[now][i]--;
19. a[i][now]--;
20. solve(i);
21. }
22. }
23. d[dn++]=now;
24. }
25. public static void main(String[] args)throws IOException{
26. Scanner fin=new Scanner(new File("fence.in"));
27. PrintWriter fout=new PrintWriter(new File("fence.out"));
28. int[] dd=new int[501];
29. m=fin.nextInt();
30. int minv=10000;
31. for (int i=0;i<m;i++){
32. int x=fin.nextInt(),y=fin.nextInt();
33. a[x][y]++;
34. a[y][x]++;
35. dd[x]++;dd[y]++;
36. if (x<minv) minv=x;
37. if (y<minv) minv=y;
38. if (x>n) n=x;
39. if (y>n) n=y;
40. }
41. for (int i=1;i<=n;i++)
42. if (dd[i]%2==1) {solve(i);break;}
43. if (dn==0) solve(minv);
44. for (int i=dn-1;i>=0;i--) fout.println(d[i]);
45. fout.close();
46. }
47. }
相关日志:
收藏:
QQ书签
del.icio.us
订阅:
Google
抓虾