bzoj 2095 [Poi2010]Bridges

Description

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

Input

输入：第一行为两个用空格隔开的整数n（2<=n<=1000），m(1<=m<=2000)，接下来读入m行由空格隔开的4个整数a，b（1<=a,b<=n,a<>b），c，d(1<=c,d<=1000)，表示第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

题解

最大值最小就是二分答案。这样去掉几条边就成了混合图。。

可以看下这个

建图就好了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 10010
using namespace std;
const int inf = 0x3f3f3f3f;
struct flows {
    struct node {
        int to, next, flow;
    } e[N * 20];
    int tot, st[N], dis[N], cur[N], in[N], out[N];
    void init() {
        tot = -1, memset(e, -1, sizeof e),
        memset(st, -1, sizeof st);
        memset(in, 0, sizeof in);
        memset(out, 0, sizeof out);
    }
    void add(int x, int y, int z) {
        e[++tot].to = y;
        e[tot].flow = z;
        e[tot].next = st[x];
        st[x] = tot;
    }
    void add_edge(int x, int y, int z) {
//      printf("add:%d %d %d\n", x, y, z);
        add(x, y, z), add(y, x, 0);
    }
    queue <int> que;
    int bfs(int S, int T) {
        memcpy(cur, st, sizeof st);
        memset(dis, 0, sizeof dis);
        while (!que.empty()) que.pop();
        que.push(S);
        dis[S] = 1;
        while(!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = st[now]; ~i; i = e[i].next)
                if (e[i].flow && !dis[e[i].to]) {
                    dis[e[i].to] = dis[now] + 1;
                    if (e[i].to == T) return 1;
                    que.push(e[i].to);
                }
        }
        return 0;
    }
    int finds(int now, int T, int flow) {
        if (now == T)
            return flow;
        int f;
        for (int i = cur[now]; ~i; i = e[i].next) {
            cur[now] = i;
            if (e[i].flow && dis[e[i].to] == dis[now] + 1 &&
                (f = finds(e[i].to, T, min(flow, e[i].flow)))) {
                e[i].flow -= f;
                e[i^1].flow += f;
                return f;
            }
        }
        return 0;
    }
    int dinic(int S, int T) {
        int flow = 0, x;
        while(bfs(S, T)) {
            while(x = finds(S, T, inf)) {
                flow += x;
            }
        }
        return flow;
    }
}flow;
int n, m, S, T, x, y, z, c;
struct datas {
    int fr, to, a, b;
}edge[N];
bool check(int x) {
    flow.init();
    S = 0, T = n + 1;
    for (int i = 1; i <= m; ++i) {
        if (edge[i].a <= x)
            flow.out[edge[i].fr]++,
            flow.in[edge[i].to]++;
        if (edge[i].b <= x)
            flow.add_edge(edge[i].to, edge[i].fr, 1);
    }
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        if (flow.in[i] > flow.out[i])
            flow.add_edge(S, i, (flow.in[i] - flow.out[i]) / 2),
            cnt += (flow.in[i] - flow.out[i]) / 2;
        else
            flow.add_edge(i, T, (flow.out[i] - flow.in[i]) / 2);
    for (int i = 1; i <= n; ++i)
        if (((flow.in[i] - flow.out[i]) & 1) || flow.in[i] == 0 && flow.out[i] == 0)
            return 0;
    if (flow.dinic(S, T) == cnt)
        return 1;
    else
        return 0;
}
main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d%d", &edge[i].fr, &edge[i].to, &edge[i].a, &edge[i].b);
        if (edge[i].a > edge[i].b)
            swap(edge[i].a, edge[i].b), swap(edge[i].fr, edge[i].to);
    }
    int l = 1, r = 1000, ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid))
            ans = mid, r = mid - 1;
        else
            l = mid + 1;
    }
    if (ans)
        printf("%d\n", ans);
    else
        puts("NIE");
}