题外话：很多混合图问题可以转化为有向图问题（将无向边拆为两条有向边）
本题不行，因为只能经过一次
这种问题能想到网络流。。
复习欧拉回路：入度==出度
和uva1380有点相似，要先给无向边定向。原图为G，定向的边单独组成另一个G’
定向后对任意点，入度==出度，则有了回路。
否则调整原来的无向边。 （如果入度出度奇偶性不同，则无解）
出度增加（in-out/2）。
注意U->V变成V->U，U出度-1，V出度+1. 就像在运送”出度”，就是网络流。（满足out>in的点能提供出度） （可以提供的出度为diff[i]/2，需要接受的出度为-diff[i]/2）
原有的边cap为1（只能改一次方向）
设立超级节点S，T，S连可以提供的节点，cap为可以提供的出度
T类似。
当sum可以提供的出度!=MaxFlow，就无解。否则有解（必须提供出去。这里可以证明提供出去后所有的点in==out）
char dir[9];
scanf("%d%d%s", &u[i], &v[i], dir); 0 1 D
感觉可以做一个处理输入的专题了...
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; const int INF = 1000000000; struct Edge { int from, to, cap, flow; Edge(int u, int v, int c, int f):from(u),to(v),cap(c),flow(f) {} }; const int maxn = 100+10; struct EdmondsKarp { int n, m; vector<Edge> edges; // 边数的两倍 vector<int> G[maxn]; // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号 int a[maxn]; // 当起点到i的可改进量 int p[maxn]; // 最短路树上p的入弧编号 void init(int n) { for(int i = 0; i < n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } int Maxflow(int s, int t) { int flow = 0; for(;;) { memset(a, 0, sizeof(a)); queue<int> Q; Q.push(s); a[s] = INF; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(!a[e.to] && e.cap > e.flow) { p[e.to] = G[x][i]; a[e.to] = min(a[x], e.cap-e.flow); Q.push(e.to); } } if(a[t]) break; } if(!a[t]) break; for(int u = t; u != s; u = edges[p[u]].from) { edges[p[u]].flow += a[t]; edges[p[u]^1].flow -= a[t]; } flow += a[t]; } return flow; } }; EdmondsKarp g; const int maxm = 500 + 5; int n, m, u[maxm], v[maxm], directed[maxm], id[maxm], diff[maxn]; vector<int> G[maxn]; vector<int> vis[maxn]; vector<int> path; void euler(int u) { for(int i = 0; i < G[u].size(); i++) if(!vis[u][i]) { vis[u][i] = 1; euler(G[u][i]); path.push_back(G[u][i]+1); } } void print_answer() { // build the new graph for(int i = 0; i < n; i++) { G[i].clear(); vis[i].clear(); } for(int i = 0; i < m; i++) { bool rev = false; if(!directed[i] && g.edges[id[i]].flow > 0) //id记录了无向边在edges中的位置 rev = true; //G记录边的起点对应的终点 if(!rev) //没有变反向 { G[u[i]].push_back(v[i]); vis[u[i]].push_back(0); } else { G[v[i]].push_back(u[i]); vis[v[i]].push_back(0); } } // print euler tour path.clear(); euler(0); //因为节点一记为了0 printf("1"); for(int i = path.size()-1; i >= 0; i--) printf(" %d", path[i]); printf(" "); } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); g.init(n+2); memset(diff, 0, sizeof(diff)); for(int i = 0; i < m; i++) { char dir[9]; scanf("%d%d%s", &u[i], &v[i], dir); u[i]--; v[i]--; directed[i] = (dir[0] == 'D' ? 1 : 0); diff[u[i]]++; //出度-入度 diff[v[i]]--; if(!directed[i]) { id[i] = g.edges.size(); g.AddEdge(u[i], v[i], 1); } } bool ok = true; for(int i = 0; i < n; i++) if(diff[i] % 2 != 0) { ok = false; break; } int s = n, t = n+1; if(ok) { int sum = 0; for(int i = 0; i < n; i++) { if(diff[i] > 0) { g.AddEdge(s, i, diff[i]/2); sum += diff[i]/2; } if(diff[i] < 0) { g.AddEdge(i, t, -diff[i]/2); } } if(g.Maxflow(s, t) != sum) ok = false; } if(!ok) printf("No euler circuit exist "); else print_answer(); // underlying graph is always connected if(T) printf(" "); } return 0; }