題意:
給你一個圖,有N個點,M條邊,有單向邊和雙向邊
讓你是否存在歐拉回路，有就輸出路徑
1.判斷是否有歐拉回路： 可以用最大流來判斷
首先，我們從結論出發： 存在歐拉回路的充要條件是 每個點的入度等於出度。
先把所用無向邊隨便定向（我們就按輸入的時候的方向定向），
問題就轉化成 “改變其中一些無向邊的方向，使所有的點入度等於出度”。
對於改變某一條無向邊, 這條邊所在的點的度數改變2(可能-2， 可能+2)。
所以有如果有某個點出入度之差為奇數，那麼肯定不存在歐拉回路(情況1)
記出入度之差為d
接下來討論除情況1以外的情況：
現在，每個點入度和出度之差均為偶數。
對於每個點，我們需要改變跟該點相連的x/2條邊， 就可以使該點的入度等於出度
新建源點S和匯點T
對於d < 0 的點i， 連S---->i ， 流量為-d
對於d > 0 的點i， 連i----->T，流量為d
對於每條無向邊<i，j> ，連i----->j， 流量為2
流一遍最大流，如果對於所有的點i，存在S----->i的邊並且漫流，那麼歐拉回路就有解。
2.輸出歐拉回路： dfs+棧保存
通過最大流以後，我們檢查無向邊<i，j> 流過的流量，我們可以確定無向邊<i，j> 的方向
然後問題就變為 "輸出無向圖的歐拉回路"。
我們用dfs搜索，訪問每條邊，對於節點u，當其u以下的兒子節點都搜過時，我們把u入棧
把棧反向輸出，就是我們要的歐拉回路。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define PII pair<int, int>
#define MP make_pair
#define X first
#define Y second
const int maxn = 510;
const int inf = 1e9;
struct Edge {
int v, next, c, op;
} edge[maxn * maxn << 1];
int E, head[maxn];
int n, m;
int S, T;
vector<PII> edges[maxn];
void add(int s, int t, int c) {
edge[E].v = t;
edge[E].c = c;
edge[E].op = 1;
edge[E].next = head[s];
head[s] = E++;
edge[E].v = s;
edge[E].c = 0;
edge[E].op = 0;
edge[E].next = head[t];
head[t] = E++;
}
int st[maxn], top;
void init() {
E = 0;
memset(head, -1, sizeof(head));
}
int gap[maxn], dis[maxn], pre[maxn], cur[maxn];
int sap(int s, int t, int n) // s 源點，t匯點，n頂點總數
{
int i;
for(i = 0; i <= n; i++) {
dis[i] = gap[i] = 0;
cur[i] = head[i];
}
gap[0] = n;
int u = pre[s] = s, maxf = 0, aug = inf, v;
while(dis[s] < n) {
loop: for(i = cur[u]; i != -1; i = edge[i].next) {
v = edge[i].v;
if(edge[i].c > 0 && dis[u] == dis[v] + 1) {
aug = min(aug, edge[i].c);
pre[v] = u;
cur[u] = i;
u = v;
if(u == t) {
while(u != s) {
u = pre[u];
edge[cur[u]].c -= aug;
edge[cur[u] ^ 1].c += aug;
}
maxf += aug;
aug = inf;
}
goto loop;
}
}
int min_d = n;
for(i = head[u]; i != -1; i = edge[i].next) {
v = edge[i].v;
if(edge[i].c > 0 && dis[v] < min_d) {
min_d = dis[v];
cur[u] = i;
}
}
if(!(--gap[dis[u]]))
break;
++gap[dis[u] = min_d + 1];
u = pre[u];
}
return maxf;
}
char buf[3];
int d[103];
int x, y;
bool vis[maxn];
void dfs(int u) {
int i;
for (i = 0; i < (int) edges[u].size(); i++) {
int v = edges[u][i].X;
int id = edges[u][i].Y;
if (vis[id])
continue;
vis[id] = 1;
dfs(v);
}
st[top++] = u + 1;
}
int id;
int main() {
int i, j, cas;
scanf("%d", &cas);
while (cas--) {
init();
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++) {
d[i] = 0;
edges[i].clear();
}
top = 0;
memset(vis, 0, sizeof(vis));
id = 0;
for (i = 0; i < m; i++) {
scanf("%d%d%s", &x, &y, buf);
d[--x]--;
d[--y]++;
if (buf[0] == 'U') {
add(x, y, 2);
} else {
edges[x].push_back(MP(y, id++));
}
}
for (i = 0; i < n; i++)
if (d[i] & 1)
break;
if (i != n) {
puts("No euler circuit exist\n");
continue;
}
S = n;
T = n + 1;
for (i = 0; i < n; i++) {
if (d[i] < 0)
add(S, i, -d[i]);
else if (d[i] > 0)
add(i, T, d[i]);
}
int sum = sap(S, T, T + 1);
for (i = head[S]; ~i; i = edge[i].next)
if (edge[i].c)
break;
if (~i) {
puts("No euler circuit exist\n");
continue;
}
for (i = 0; i < n; i++)
for (j = head[i]; ~j; j = edge[j].next)
if (edge[j].op) {
int v = edge[j].v;
if (v >= n)
continue;
if (edge[j ^ 1].c) {
edges[v].push_back(MP(i, id++));
} else
edges[i].push_back(MP(v, id++));
}
dfs(0);
for (i = top - 1; i >= 1; i--)
printf("%d ", st[i]);
printf("%d\n\n", st[0]);
}
return 0;
}
