BZOJ2095【POI2010】Bridges <二分+网络流>

Problem

【POI2010】Bridges

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;259\;MB}$

Description

$\mathrm{YYD}$为了减肥，来到了瘦海。
这是一个巨大的海，海中有$n$个小岛，小岛之间有$m$座桥连接，两个小岛之间不会有两座桥，并且从一个小岛可以到另外任意一个小岛。
现在$\mathrm{YYD}$想骑单车从小岛$1$出发，骑过每一座桥，到达每一个小岛，然后回到小岛$1$。
霸中同学为了让$\mathrm{YYD}$减肥成功，召唤了大风，由于是海上风变得十分大，经过每一座桥都有不可避免的风阻碍$\mathrm{YYD}$，$\mathrm{YYD}$十分$\mathrm{ddt}$，于是用泡芙贿赂了你，希望你能帮他找出一条承受的最大风力最小的路线。

Input

第一行为两个用空格隔开的整数$n,m$。
接下来$m$行，每行为由空格隔开的$4$个整数$a,b,c,d$，第$i+1$行表示第$i$座桥连接小岛$a$和$b$，从$a$到$b$承受的风力为$c$，从$b$到$a$承受的风力为$d$。

Output

如果无法完成减肥计划，则输出NIE，否则第一行输出最大风力的最小值。

Sample Input

4 4
1 2 2 4
2 3 3 4
3 4 4 4
4 1 5 4

Sample Output

4

Explanation

HINT

$2\le n\le10^3$,$1\le m\le2\times10^3$
对于每座桥，保证$1\le a,b\le n$,$a\ne b$,$1\le c,d\le 10^3$

标签：二分答案 网络流 欧拉回路

Solution

二分答案+网络流判定混合图欧拉回路

二分答案，找出符合条件的边集，原问题变为判断混合图中是否存在欧拉回路。
用经典的网络流判定混合图欧拉回路的建模方式：

• 给所有无向边随机定向，若$u-v$的无向边定向为$u\to v$，则连边$v\to u$流量为$1$
• 按照定向后的图计算每个点的入度$into$和出度$outo$
• 对于每个点$i$，若$into>outo$，则连边$s\to i$流量为$\frac{into-outo}{2}$；若$outo>into$，则连边$i\to t$流量为$\frac{outo-into}{2}$

建图后跑一遍$\mathrm{Dinic}$，若满载，则存在欧拉回路。

大致原理：欧拉回路的充要条件是存在一种定向使得每个点的入度等于出度。随机定向后，连接“$v\to u$”的边，这样走这条边可以使得$u$的出度$+1$，$v$的入度$-1$，达到边反向的效果。而一个点入度每$-1$，出度均要$+1$，所以分正负从$s$或向$t$连长为$\frac{|into-outo|}{2}$的边，这样满载时这个点一定有$into=outo$。

Code

#include <bits/stdc++.h>
#define MAX_N 1000
#define MAX_M 10000
#define mid ((l+r)>>1)
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, into[MAX_N+5], outo[MAX_N+5];
int s, t, cnt, d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5];
struct edge {int u, v, x, y;} e[MAX_M+5];
void init() {s = 0, t = n+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que; que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow; int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = s; i <= t; i++) cr[i] = pr[i];}
void rec() {for (int i = s; i <= t; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0; cpy(); while (BFS()) ret += DFS(s, INF), rec(); return ret;}
bool chk(int tans) {
    int tot = 0; init();
    for (int i = 1; i <= m; i++) if (e[i].x > tans) return false;
    memset(into, 0, sizeof into), memset(outo, 0, sizeof outo);
    for (int i = 1; i <= m; i++) into[e[i].v]++, outo[e[i].u]++;
    for (int i = 1; i <= m; i++) if (e[i].y <= tans) addedge(e[i].v, e[i].u, 1);
    for (int i = 1; i <= n; i++) if (into[i]%2 != outo[i]%2) return false;
    for (int i = 1; i <= n; i++) tot += max(0, (outo[i]-into[i])>>1);
    for (int i = 1; i <= n; i++)
        if (into[i] > outo[i]) addedge(s, i, (into[i]-outo[i])>>1);
        else if (into[i] < outo[i]) addedge(i, t, (outo[i]-into[i])>>1);
    return Dinic() == tot;
}
void bi_search(int l, int r) {
    int ans = 0;
    while (l <= r)
        if (!chk(mid)) l = mid+1;
        else ans = mid, r = mid-1;
    if (!ans) puts("NIE");
    else printf("%d\n", ans);
}
int main() {
    read(n), read(m);
    for (int i = 1, u, v, x, y; i <= m; i++) {
        read(u), read(v), read(x), read(y);
        if (x < y) e[i] = (edge){u, v, x, y};
        else e[i] = (edge){v, u, y, x};
    }
    return bi_search(1, 1000), 0;
}