题目传送门(BZOJ)

题解 :

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

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>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<int> 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原创, 转载必须以链接形式注明>原文链接<