UVA 10735 最大流 混合欧拉回路 输出路径
题意:
给你一个图,有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; }
补充:软件开发 , C++ ,