BZOJ 1532: [POI2005]KOS – [二分/最大流]

题目传送门(BZOJ)

题解 :

最大值最小, 又一个鲜明的二分标志
考虑二分最大值验证
我们把求最大值最小问题, 转化成了赢最多的人赢不超过 mid 次, 能否完成比赛
通过网络流验证答案 mid 的可行性
由 S 连向每场比赛, 容量为 1, 代表每场比赛只能有一个人赢
由每场比赛连向参与的两个人, 容量为 1, 同样代表每场比赛只能有一个人赢
再由每个人连向 T, 流量为 mid, 代表每个人最多赢 mid 次
最后判断是否能把 m 场比赛都流完, 继续二分即可
代码中注释掉的部分是输出方案, Luogu有SPJ, 这题输出方案也不难

代码 :

#include 
#include 
#include 
#include 
#include 
using namespace std;
#define rev(i, p) for(EDGE* i = h[p]; i; i = i->next)
const int N = 40000;
const int INF = 1<<30;
const int S = N-1, T = N-2;
#define nc() p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++
char buf[100000], *p1, *p2;
inline char gc() {
    char ch = nc();
    while(isspace(ch)) ch = nc();
    return ch;
}
inline int rd() {
    int x = 0, f = 1; char ch = nc();
    while(!isdigit(ch)) ch = nc();
    while( isdigit(ch)) x = (((x<<2)+x)<<1)+(ch^48), ch = nc();
    return x*f;
}
struct EDGE {
    int to, val;
    EDGE *next, *back;
    int is;
}*h[N], e[N<<3];
int _;
inline void addEdge(int u, int v, int w, int x = 0) {
    EDGE*
    t = &e[++_]; t->to = v, t->val = w, t->back = &e[_+1], t->next = h[u], h[u] = t;
    t->is = x;
    t = &e[++_]; t->to = u, t->val = w, t->back = &e[_-1], t->next = h[v], h[v] = t;
}
int dep[N];
queue q;
bool bfs() {
    memset(dep, 0, sizeof dep);
    while(!q.empty()) q.pop();
    dep[S] = 1; q.push(S);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        rev(i, u) if(!dep[i->to] && i->val) {
            dep[i->to] = dep[u]+1;
            if(i->to == T) return 1;
            q.push(i->to);
        }
    }
    return 0;
}
int dfs(int p, int mf) {
    if(p == T) return mf;
    int nf = 0;
    rev(i, p) if(dep[i->to] == dep[p]+1 && i->val) {
        int tmp = dfs(i->to, min(mf-nf, i->val));
        if(!tmp) dep[i->to] = 0;
        nf += tmp;
        i->val -= tmp;
        i->back->val += tmp;
        if(nf == mf) break;
    }
    return nf;
}
inline int Dinic() {
    int ans = 0, tmp;
    while(bfs()) {
        while((tmp=dfs(S, INF))) ans += tmp;
    }
    return ans;
}
int n, m;
int a[N][2];
int main() {
    n = rd(), m = rd();
    for(int i = 1; i <= m; i ++ ) for(int j = 0; j <= 1; j ++ ) a[i][j] = rd();
    int l = 1, r = m;
    while(l < r) {
        int mid = (l+r) >> 1;
        _ = 0; memset(h, 0, sizeof h);
        for(int i = 1; i <= m; i ++ ) addEdge(S, i, 1);
        for(int i = 1; i <= n; i ++ ) addEdge(i+m, T, mid);
        for(int i = 1; i <= m; i ++ ) for(int j = 0; j <= 1; j ++ ) addEdge(i, m+a[i][j], 1, j+1);
        if(Dinic() == m) r = mid;
        else l = mid+1;
    }
    printf("%d\n", l);
    /* _ = 0; memset(h, 0, sizeof h);
    for(int i = 1; i <= m; i ++ ) addEdge(S, i, 1);
    for(int i = 1; i <= n; i ++ ) addEdge(i+m, T, l);
    for(int i = 1; i <= m; i ++ ) for(int j = 0; j <= 1; j ++ ) addEdge(i, m+a[i][j], 1, j+1);
    Dinic();
    for(int i = 1; i <= m; i ++ ) rev(j, i) {
        if(j->is && j->val) printf("%d\n", j->is!=1); 
    }*/
}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<