20200717 专题：欧拉回路

总览：

欧拉通路定义：对于一个图，存在一条路径经过且只经过每边一次
欧拉回路定义：对于一个图，存在一条路径经过且只经过每边一次，且起点与终点相同

无向图判定：
每个点的出度和入度都为偶数

有向图判定：
每个点的出度和入度相同

寻找欧拉回路（保证存在）：
当遍历完一条边的所有路径后倒序输出这条路径

inline void DFS(int x) {for (int y = head[x]; y; y = road[y].nex) {int z = road[y].to, d = road[y].id;if (road[y].ex) continue;road[y].ex = 1;DFS(z);res[++pos] = d;}return;
}for (int i = pos; i; i--) printf("%d ", res[i]);

混合图的欧拉回路：
欧拉回路中无向边只有一个方向
先确定无向边的方向
对于一条无向边，先钦定一个方向
统计每一个点的出度和入度
令入度减出度为度数 w
当所有点度数为零时，存在欧拉回路
发现对于一条无向边 $s->t$ 改向， $w_s$ 和 $w_t$ 都改变 2
如果存在 $w_i\%2$ 不为 0，则不存在欧拉回路
考虑用网络流完成自我调整的过程
对于 $w_i>0$，源点向 i 连流量为 $w_i/2$ 的边
对于 $w_i<0$，i 向汇点连流量为 $-w_i/2$ 的边
对于钦点的无向边 $s->t$，t 向 s 连流量为 1 的边，表示可以反向
跑网络流
当源点连出的边都满流时，存在欧拉回路
如果在网络流上 $s->t$ 被流过，则在欧拉回路中 s 和 t 的方向与钦定方向相反
这样就可以重新建图，跑有向图欧拉回路了

代码见例题

T1 #2460. 「POI2010」桥 Bridges

思路：
二分答案后混合图欧拉回路

代码：

#include <bits/stdc++.h>
using namespace std;namespace IO {
inline char ch() {static char buf[1 << 21], *p1 = buf, *p2 = buf;return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)? EOF: *p1++;
}
inline int in() {int s = 0, f = 1;char x;for (x = getchar(); x < '0' || x > '9'; x = getchar())if (x == '-') f = -1;for (; x >= '0' && x <= '9'; x = getchar()) s = (s * 10) + (x & 15);return f == 1 ? s : -s;
}
}  // namespace IO
using namespace IO;const int A = 1e6 + 5;
const int N = 3e3 + 5;
const int INF = 1e9;
int n, m;
struct Road {Road(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) {nex = a, to = b, w = c, id = d, ex = e;}int nex, to, w, id, ex;
};
int rev[N][N];
int res[A], pos;namespace EP {
int head[N], tot_road = 1;
int cur[N], tot;
int vis[N][N];
Road road[2 * A], net[2 * A];
inline void edge(int x, int y, int w, int d) {road[++tot_road] = Road(head[x], y, w, d);head[x] = tot_road;
}
inline void ljb(int x, int y, int w, int d) {net[++tot] = Road(cur[x], y, w, d);cur[x] = tot;
}
inline void build(int maxx) {for (int i = 1; i <= n; i++) {for (int y = head[i]; y; y = road[y].nex) {int z = road[y].to, w = road[y].w, k = road[y ^ 1].w, d = road[y].id;if (w > maxx) continue;if (k > maxx)ljb(i, z, 0, d);else {if (i > z)continue;else {if (!rev[i][z])ljb(i, z, 0, d);elseljb(z, i, 0, d);}}}}return;
}
inline void DFS(int x) {for(int y=cur[x];y;y=net[y].nex){int z=net[y].to,d=net[y].id;if(net[y].ex)	continue;net[y].ex=1;DFS(z);res[++pos]=d;}return;
}
}  // namespace EPnamespace NET {
#define S 0
#define T n + 1
int head[N], tot_road = 1;
Road road[2 * A];
inline void edge(int x, int y, int w) {road[++tot_road] = Road(head[x], y, w);head[x] = tot_road;road[++tot_road] = Road(head[y], x, 0);head[y] = tot_road;
}
int rd[N], cd[N];
int all;
int f[N];
inline int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
inline void merge(int x, int y) {int xx = find(x), yy = find(y);if (xx != yy) f[xx] = yy;return;
}
inline int work(int maxx) {for (int i = 1; i <= n; i++) rd[i] = cd[i] = 0, f[i] = i;for (int i = 1; i <= n; i++) {for (int y = EP::head[i]; y; y = EP::road[y].nex) {int z = EP::road[y].to, w = EP::road[y].w, k = EP::road[y ^ 1].w;if (w > maxx) continue;if (k <= maxx && z < i) continue;rd[z]++, cd[i]++;merge(i, z);}}for (int i = 1; i <= n; i++) {if (find(i) != find(1)) return 0;if ((rd[i] - cd[i]) % 2 == 1) return 0;}return 1;
}
inline void build(int maxx) {for (int i = S; i <= T; i++) head[i] = 0;tot_road = 1;all = 0;for (int i = 1; i <= n; i++) {if (rd[i] != cd[i]) {if (rd[i] > cd[i]) {edge(S, i, (rd[i] - cd[i]) >> 1);all += ((rd[i] - cd[i]) >> 1);} elseedge(i, T, (cd[i] - rd[i]) >> 1);}for (int y = EP::head[i]; y; y = EP::road[y].nex) {int z = EP::road[y].to, w = EP::road[y].w, k = EP::road[y ^ 1].w;if (w > maxx || k > maxx) continue;if (z < i) continue;edge(z, i, 1);}}return;
}
int maxflow = 0;
int dep[N], sum[N];
inline void BFS() {queue<int> q;for (int i = S; i <= T; i++) dep[i] = -1, sum[i] = 0;dep[T] = 0, sum[dep[T]]++;q.push(T);while (!q.empty()) {int x = q.front();q.pop();for (int y = head[x]; y; y = road[y].nex) {int z = road[y].to;if (dep[z] != -1) continue;dep[z] = dep[x] + 1;sum[dep[z]]++;q.push(z);}}return;
}
inline int DFS(int x, int flow) {if (x == T) {maxflow += flow;return flow;}int used = 0;for (int y = head[x]; y; y = road[y].nex) {int z = road[y].to, w = road[y].w;if (dep[z] + 1 == dep[x] && w) {int after = DFS(z, min(w, flow - used));if (after) {used += after;road[y].w -= after;road[y ^ 1].w += after;}}if (flow == used) return used;}if (!--sum[dep[x]]) dep[T] = n + 1;sum[++dep[x]]++;return used;
}
inline void ISAP() {maxflow = 0;BFS();while (dep[T] <= n) DFS(S, INF);return;
}
inline int check(int maxx) {if (!work(maxx)) return 0;build(maxx);ISAP();if (maxflow < all) return 0;return 1;
}
inline void revese(int now) {check(now);for (int i = 2; i <= tot_road; i += 2) {if (road[i].w) continue;int x = road[i].to, y = road[i ^ 1].to;if (x >= 1 && x <= n && y >= 1 && y <= n) rev[x][y] = rev[y][x] = 1;}return;
}
#undef S
#undef T
}  // namespace NETsigned main() {n = in(), m = in();for (int i = 1; i <= m; i++) {int u = in(), v = in(), a = in(), b = in();EP::edge(u, v, a, i), EP::edge(v, u, b, i);}int L = 0, R = 1000, ans = -1;while (L <= R) {int mid = (L + R) >> 1;if (NET::check(mid))R = mid - 1, ans = mid;elseL = mid + 1;}if (ans == -1) {puts("NIE");return 0;}printf("%d\n", ans);NET::revese(ans);EP::build(ans);EP::DFS(1);for (int i = m; i ; i--) printf("%d ", res[i]);puts("");return 0;
}