P3511 [POI2010] MOS-Bridges

若存在 $2\nmid deg_i$ 则无解。

二分答案，若存在一条边的两个方向均走不了，则当前答案无解，否则一些边的方向已经确定，其余边有两种方向可选择。

考虑有向图存在欧拉回路的充要条件，所有点的出度和入度相等，据此已经可以算出每个点最终的出度。注意到若 $(u, v)$ 定向为 $u\to v$ 则 $u$ 的出度增加 $1$，反之 $v$ 的出度增加 $1$，这自然地给予我们网络流模型：将每条边抽象成点，$S\to e$ 容量 $1$，若 $l\leq mid$ 则 $e\to u$ 容量 $1$，若 $p\leq mid$ 则 $e\to v$ 容量 $1$，$i\to T$ 容量 $\frac{deg_i} 2$，用最大流检查是否存在给所有边定向且满足限制的方案。若存在则当前答案有解，否则无解。

求出最终答案后根据边的定向方案还原有向图，跑欧拉回路即可。时间复杂度 $\mathcal{O}(m\sqrt m\log V)$。

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2.1e4 + 5;
constexpr int M = 7e4 + 5;
struct flow {
  int cnt = 1, hd[N], nxt[N << 1], to[N << 1], limit[N << 1];
  void add(int u, int v, int w) {
    nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v, limit[cnt] = w;
    nxt[++cnt] = hd[v], hd[v] = cnt, to[cnt] = u, limit[cnt] = 0;
  }
  int T, cur[N], dis[N];
  int dfs(int id, int res = 1e9) {
    if(id == T) return res;
    int flow = 0;
    for(int i = cur[id]; i && res; i = nxt[i]) {
      cur[id] = i;
      int it = to[i], c = min(res, limit[i]);
      if(dis[id] + 1 == dis[it] && c) {
        int k = dfs(it, c);
        flow += k, res -= k, limit[i] -= k, limit[i ^ 1] += k;
      }
    }
    if(!flow) dis[id] = -1;
    return flow;
  }
  int maxflow(int s, int t) {
    int flow = 0;
    T = t;
    while(1) {
      queue<int> q;
      memset(dis, -1, sizeof(dis));
      memcpy(cur, hd, sizeof(cur));
      q.push(s), dis[s] = 0;
      while(!q.empty()) {
        int t = q.front();
        q.pop();
        for(int i = hd[t]; i; i = nxt[i])
          if(dis[to[i]] == -1 && limit[i])
            dis[to[i]] = dis[t] + 1, q.push(to[i]);
      }
      if(dis[t] == -1) return flow;
      flow += dfs(s);
    }
  }
} I, g;
int n, m, t, top, stc[N], hd[N], deg[N];
int x[N], y[N], c[N], d[N];
vector<pair<int, int>> e[N];
bool calc(int mid) {
  g = I;
  for(int i = 1; i <= m; i++)
    if(c[i] > mid && d[i] > mid) return 0;
    else {
      if(c[i] <= mid) g.add(i + n, x[i], 1);
      if(d[i] <= mid) g.add(i + n, y[i], 1);
    }
  return g.maxflow(0, t) == m;
}
void dfs(int id) {
  for(int &i = hd[id]; i < e[id].size(); ) {
    auto it = e[id][i++];
    dfs(it.first), stc[++top] = it.second;
  }
}
int main() {
#ifdef ALEX_WEI
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif
  cin >> n >> m, t = N - 1;
  for(int i = 1; i <= m; i++) {
    cin >> x[i] >> y[i] >> c[i] >> d[i];
    deg[x[i]]++, deg[y[i]]++;
    I.add(0, i + n, 1);
  }
  for(int i = 1; i <= n; i++)
    if(deg[i] & 1) puts("NIE"), exit(0);
    else I.add(i, t, deg[i] >> 1);
  int l = 1, r = 1e3;
  while(l < r) {
    int mid = l + r >> 1;
    if(calc(mid)) r = mid;
    else l = mid + 1;
  }
  cout << l << "\n";
  calc(l);
  for(int i = 1; i <= m; i++)
    for(int j = g.hd[i + n]; j; j = g.nxt[j]) {
      int it = g.to[j];
      if(it == x[i] && !g.limit[j]) e[x[i]].push_back({y[i], i});
      if(it == y[i] && !g.limit[j]) e[y[i]].push_back({x[i], i});
    }
  dfs(1);
  for(int i = top; i; i--) cout << stc[i] << " ";
  cout << "\n";
  return 0;
}
/*
2022/6/16
start thinking at 19:50
感觉像个网络流啊老哥。
没错，就是网络流，啊哈哈哈。
start coding at 20:08
finish debugging at 20:31
*/