POJ 2230

题目大意：给出一副联通无向图，求从起点1开始，每条边走两次，回到起点的的一种路径方案。{SPJ}

解：我感觉和欧拉回路有点像，然后是分析性质，把每条无向边拆成两条，可以发现，从任意点的欧拉回路都是存在的（奇数乘偶数=偶数>.<）, 然后我是用了一种无赖走法，把剩余的点看成一个大点，然后走去这个大点再走回来，进入大点后不断缩小规模。主要的问题是判断点是否走过（度走完）以及边是否走过。

View Code

 1 //poj 2230
 2 const
 3         maxn=11111;
 4         maxm=51111;
 5 type
 6         data=record
 7           dest, next, op, cost: longint;
 8         end;
 9 var
10         edge: array[1..maxm*2]of data;
11         vect, deg: array[1..maxn]of longint;
12         n, m, tot: longint;
13 procedure add(x, y: longint);
14 begin
15   inc(tot);
16   with edge[tot] do begin
17     dest := y;
18     next := vect[x];
19     cost := 1;
20     vect[x] := tot;
21     op := tot+1;
22   end;
23   inc(tot);
24   with edge[tot] do begin
25     dest := x;
26     cost := 1;
27     next := vect[y];
28     vect[y] := tot;
29     op := tot-1;
30   end;
31 end;
32 
33 procedure init;
34 var
35         i, j, x, y: longint;
36 begin
37   fillchar(vect, sizeof(vect), 0);
38   fillchar(deg, sizeof(deg), 0);
39   tot := 0;
40   readln(n, m);
41   for i := 1 to m do begin
42     readln(x, y);
43     add(x, y);
44     inc(deg[x], 2); inc(deg[y], 2);
45   end;
46 end;
47 
48 procedure search(x: longint);
49 var
50         i, u: longint;
51 begin
52   i := vect[x];
53   while i<>0 do
54     with edge[i] do begin
55       if (deg[dest]>0)and(deg[x]>0)and(cost>0) then begin
56         dec(deg[x], 2);
57         dec(deg[dest], 2);
58         cost := 0;
59         edge[op].cost := 0;
60         writeln(dest);
61         search(dest);
62         writeln(x);
63       end;
64       i := next;
65     end;
66 end;
67 
68 procedure main;
69 begin
70   writeln(1);
71   search(1);
72 end;
73 
74 begin
75   assign(input,'1.txt'); reset(input);
76   init;
77   main;
78 end.