题目地址：洛谷：【P3425】[POI2005]KOS-Dicing – 洛谷、BZOJ：Problem 1532. — [POI2005]Kos-Dicing

题目描述

掷骰子是一种双人游戏，它的结果是完全随机的。最近它在整个Byteotia变得非常流行。在Byteotia的首都甚至有一个特别的掷骰子业余爱好者俱乐部。俱乐部的老主顾们花时间互相聊天并每隔一阵子就和一个随机选择的对手玩这他们最喜欢的游戏。一天中赢得最多游戏的人会得到“幸运者”头衔。有时晚上俱乐部很安静，只有很少的比赛。这是哪怕赢一场也能获得“幸运者”头衔的时间。
很久很久以前有一个很不走运的人，叫Byteasar，赢得了这个光荣的头衔。他被深深地震惊了以至于完全忘了他已经赢了多少场。现在他想知道他有多幸运，以及幸运之神是否最终会向他微笑——也许他的运气会变好？他确切地知道在那个幸运的晚上有多少场游戏以及是谁玩的。然而，他不知道结果。Byteasar希望查明至少要赢几场才能获得“幸运者”头衔。做个好人，帮他满足他的好奇心吧！
任务：写一个程序：
对于每场游戏从stdin读入这场游戏的一对玩家 找到最小的数k，使得存在一个游戏结果的集合，其中赢最多的玩家赢了k场。向stdout输出数k和找到的集合中游戏的结果

题意简述

Dicing 是一个两人玩的游戏,现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.

输入输出格式

输入格式：
stdin的第一行有一个一对由一个空格分开整数n和m (1 <= n, m <= 10000) 。n表示玩家数，m表示游戏数。玩家从1到n编号。在接下来的m行中有每场游戏的一对玩家的编号，由一个空格分开，描述了游戏的序列。一对玩家可能会在这个序列中多次出现。

输出格式：
stdout的第一行应该包含一个确定的数k。对于在输入的第i行指定的一对玩家a, b，如果在找到的结果集合中a胜过b，则在输出的第i行输出1, 否则输出0.

输入输出样例

输入样例#1：

4 4
1 2
1 3
1 4
1 2

输出样例#1：

1
0
0
0
1

题解

考虑二分答案然后判定。判定可以采用网络流，建立源→每场游戏→游戏玩家→汇的网络，源→游戏及游戏→玩家的边容量为1，玩家→汇的边容量为二分的答案。如果答案是x，说明游戏中每个人胜出的次数都不大于x，因此只需在该网络上判定是否满流，满流说明该答案可行。
复杂度玄学。

代码

// Code by KSkun, 2018/6
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <queue>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 20005, INF = 1e9;

struct Edge {
    int to, cap, nxt;
} gra[MAXN << 4];
int head[MAXN], tot;

inline void addedge(int u, int v, int cap) {
    gra[tot] = Edge {v, cap, head[u]}; head[u] = tot++;
    gra[tot] = Edge {u, 0, head[v]}; head[v] = tot++;
}

int level[MAXN];

inline bool bfs(int s, int t) {
    memset(level, -1, sizeof(level));
    std::queue<int> que;
    que.push(s); level[s] = 0;
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = head[u]; ~i; i = gra[i].nxt) {
            int v = gra[i].to;
            if(gra[i].cap && level[v] == -1) {
                level[v] = level[u] + 1;
                if(v == t) return true;
                que.push(v);
            }
        }
    }
    return level[t] != -1;
}

int cur[MAXN];

inline int dfs(int u, int t, int left) {
    if(u == t || !left) return left;
    int flow = 0;
    for(int &i = cur[u]; ~i; i = gra[i].nxt) {
        int v = gra[i].to;
        if(level[v] == level[u] + 1 && gra[i].cap) {
            int f = dfs(v, t, std::min(left, gra[i].cap));
            if(f) {
                flow += f; left -= f;
                gra[i].cap -= f; gra[i ^ 1].cap += f;
                if(!left) break;
            }
        }
    }
    return flow;
}

inline int dinic(int s, int t) {
    int flow = 0;
    while(bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        int f;
        while(f = dfs(s, t, INF)) flow += f;
    }
    return flow;
}

int n, m, a[MAXN], b[MAXN], S, T;

inline bool check(int x) {
    tot = 0; memset(head, -1, sizeof(head));
    for(int i = 1; i <= n; i++) {
        addedge(i, T, x);
    }
    for(int i = 1; i <= m; i++) {
        addedge(S, i + n, 1);
        addedge(i + n, a[i], 1);
        addedge(i + n, b[i], 1);
    }
    return dinic(S, T) >= m;
}

int main() {
    n = readint(); m = readint(); S = n + m + 1; T = S + 1;
    for(int i = 1; i <= m; i++) {
        a[i] = readint(); b[i] = readint();
    }
    int l = 0, r = m, mid;
    while(r - l > 1) {
        mid = (l + r) >> 1;
        if(check(mid)) r = mid; else l = mid;
    }
    printf("%d\n", r);
    check(r);
    for(int i = 1; i <= m; i++) {
        for(int j = head[i + n]; ~j; j = gra[j].nxt) {
            int v = gra[j].to;
            if(!gra[j].cap) {
                printf("%d\n", v == a[i]); break;
            }
        }
    }
    return 0;
}