就是求混合图是否存在欧拉回路
如果存在则输出一组路径
（我就说嘛 咱的代码怎么可能错。。。。。最后的输出格式竟然w了一天 我都没发现）
解析：
对于无向边定向建边放到网络流图中add(u, v, 1);
对于有向边放到另一个图中add2(u, v);
然后就是混合边求是否有欧拉
一边dinic后 遍历每一条边 如果不是反向边 且 起点不是s 终点不是t
如果Node[i].c == 0 则 add2(Node[i].v, Node[i].u);
else add2(Node[i].u, Node[i].v);
然后用有向图的fleury输出边就好了
1 #include <iostream>
2 #include <cstdio>
3 #include <sstream>
4 #include <cstring>
5 #include <map>
6 #include <cctype>
7 #include <set>
8 #include <vector>
9 #include <stack>
10 #include <queue>
11 #include <algorithm>
12 #include <cmath>
13 #include <bitset>
14 #define rap(i, a, n) for(int i=a; i<=n; i++)
15 #define rep(i, a, n) for(int i=a; i<n; i++)
16 #define lap(i, a, n) for(int i=n; i>=a; i--)
17 #define lep(i, a, n) for(int i=n; i>a; i--)
18 #define rd(a) scanf("%d", &a)
19 #define rlld(a) scanf("%lld", &a)
20 #define rc(a) scanf("%c", &a)
21 #define rs(a) scanf("%s", a)
22 #define pd(a) printf("%d\n", a);
23 #define plld(a) printf("%lld\n", a);
24 #define pc(a) printf("%c\n", a);
25 #define ps(a) printf("%s\n", a);
26 #define MOD 2018
27 #define LL long long
28 #define ULL unsigned long long
29 #define Pair pair<int, int>
30 #define mem(a, b) memset(a, b, sizeof(a))
31 #define _ ios_base::sync_with_stdio(0),cin.tie(0)
32 //freopen("1.txt", "r", stdin);
33 using namespace std;
34 const int maxn = 100010, INF = 2e9;
35 int n, m, s, t, cnt;
36 int in[maxn], out[maxn], vis[maxn];
37 int d[maxn], head[maxn], cur[maxn];
38 set<int> ss;
39 int st[maxn],cnt3;
40 int cnt2, head2[maxn];
41
42
43 struct edge
44 {
45 int u, v, c, next, ff;
46 }Edge[maxn << 1];
47
48 void add_(int u, int v, int c, int ff)
49 {
50 Edge[cnt].u = u;
51 Edge[cnt].v = v;
52 Edge[cnt].c = c;
53 Edge[cnt].ff = ff;
54 Edge[cnt].next = head[u];
55 head[u] = cnt++;
56 }
57
58 void add(int u, int v, int c)
59 {
60 add_(u, v, c, 1);
61 add_(v, u, 0, 0);
62 }
63
64 bool bfs()
65 {
66 queue<int> Q;
67 mem(d, 0);
68 Q.push(s);
69 d[s] = 1;
70 while(!Q.empty())
71 {
72 int u = Q.front(); Q.pop();
73 for(int i = head[u]; i != -1; i = Edge[i].next)
74 {
75 edge e = Edge[i];
76 if(!d[e.v] && e.c > 0)
77 {
78 d[e.v] = d[e.u] + 1;
79 Q.push(e.v);
80 if(e.v == t) return 1;
81 }
82 }
83 }
84 return d[t] != 0;
85 }
86
87 int dfs(int u, int cap)
88 {
89 int ret = 0;
90 if(u == t || cap == 0)
91 return cap;
92 for(int &i = cur[u]; i != -1; i = Edge[i].next)
93 {
94 edge e = Edge[i];
95 if(d[e.v] == d[u] + 1 && e.c > 0)
96 {
97 int V = dfs(e.v, min(cap, e.c));
98 Edge[i].c -= V;
99 Edge[i^1].c += V;
100 ret += V;
101 cap -= V;
102 if(cap == 0) break;
103 }
104 }
105 if(cap > 0) d[u] = -1;
106 return ret;
107 }
108
109 int Dinic(int u)
110 {
111 int ans = 0;
112 while(bfs())
113 {
114 memcpy(cur, head, sizeof(head));
115 ans += dfs(u, INF);
116 }
117 return ans;
118 }
119
120
121 struct node
122 {
123 int u, v, flag, next;
124 }Node[maxn << 1];
125
126 void add2(int u, int v)
127 {
128 Node[cnt2].u = u;
129 Node[cnt2].v = v;
130 Node[cnt2].next = head2[u];
131 Node[cnt2].flag = 0;
132 head2[u] = cnt2++;
133 }
134 int used[maxn];
135 void fleury(int u)
136 {
137 for(int i = head2[u]; i != -1; i = Node[i].next)
138 {
139 if(!used[i])
140 {
141 used[i] = 1;
142 fleury(Node[i].v);
143 }
144
145 }
146 st[cnt3++] = u;
147 }
148
149
150 void init()
151 {
152 mem(in, 0);
153 mem(head, -1);
154 mem(out, 0);
155 mem(st, 0);
156 cnt = 0;
157 cnt2 = 0;
158 cnt3 = 0;
159 mem(head2, -1);
160 mem(used, 0);
161 ss.clear();
162
163 }
164
165 char str[2];
166
167 int main()
168 {
169 int T;
170 cin >> T;
171 while(T--)
172 {
173 int u, v, w;
174 cin >> n >> m;
175 init();
176 s = 0, t = maxn - 1;
177 for(int i = 1; i <= m; i++)
178 {
179 scanf("%d%d%s", &u, &v, str);
180 in[v]++, out[u]++;
181 if(str[0] == 'U') add(u, v, 1);
182 else if(str[0] == 'D') add2(u, v);
183 }
184 int flag = 0, m_sum = 0;
185 for(int i = 1; i <= n; i++)
186 {
187 if(abs(out[i] - in[i]) & 1)
188 {
189 flag = 1;
190 break;
191 }
192 if(out[i] > in[i]) add(s, i, (out[i] - in[i]) / 2), m_sum += (out[i] - in[i]) / 2;
193 else if(in[i] > out[i]) add(i, t, (in[i] - out[i]) / 2);
194
195 }
196 if(!flag && m_sum == Dinic(s))
197 {
198 for(int i = 0; i < cnt; i++)
199 {
200 if(!Edge[i].ff || Edge[i].u == s || Edge[i].v == t || Edge[i].u == t || Edge[i].v == s) continue;
201 if(Edge[i].c == 0) add2(Edge[i].v, Edge[i].u);
202 else add2(Edge[i].u, Edge[i].v);
203 }
204 fleury(1);
205 for(int i = cnt3 - 1; i >= 0; i--)
206 {
207 if(i != cnt3 - 1) printf(" ");
208 printf("%d", st[i]);
209 }
210
211
212 printf("\n");
213
214
215 }
216 else
217 cout << "No euler circuit exist" << endl;
218 if(T) printf("\n");
219
220 }
221
222 return 0;
223 }