题意
\(n\)个人\(m\)场比赛\((1 \le n \le 10000, 0 \le m \le 10000)\)，给出每场比赛的两个选手，求赢得最多的人最少赢的场数。
分析
二分最多人赢的场数，那么我们就得到了所有人赢的场次的上界。所以我们可以考虑网络流模型。
题解
对于二分的值\(d\)，我们建\(m\)个点表示比赛，\(n\)个点表示人。对于每场比赛\(i\)，连边\((s, i)\)，上界为\(1\)，连边\((i, u_i), (i, v_i)\)，上界为\(1\)。对于每个人\(i\)，连边\((i, t)\)，上界为\(d\)。然后判断最大流是否是\(m\)即可。
然而这题卡isap，所以用dinic来做到单次最大流\(O((m+n)\sqrt{n})\)。（然而isap用一些奇葩的减枝也能过。
#include <bits/stdc++.h>
using namespace std;
inline int getint() {
int x=0;
char c=getchar();
for(; c<'0'||c>'9'; c=getchar());
for(; c>='0'&&c<='9'; x=x*10+c-'0', c=getchar());
return x;
}
const int vN=20015, N=10015, oo=~0u>>1;
int ihead[vN], cnt=1, win[N], X[N], Y[N];
struct E {
int next, to, cap;
}e[vN<<3];
void add(int x, int y) {
e[++cnt]=(E){ihead[x], y, 0}; ihead[x]=cnt;
e[++cnt]=(E){ihead[y], x, 0}; ihead[y]=cnt;
}
int isap(int s, int t, int n) {
static int gap[vN], cur[vN], d[vN], p[vN];
memset(d, 0, sizeof(int)*(n+1));
memset(cur, 0, sizeof(int)*(n+1));
memset(gap, 0, sizeof(int)*(n+1));
gap[0]=n;
int r=0;
for(int x=s, f, i; d[s]<n && d[s]<100;) {
for(i=cur[x]; i && !(e[i].cap && d[x]==d[e[i].to]+1); i=e[i].next);
if(i) {
p[e[i].to]=cur[x]=i;
if((x=e[i].to)==t) {
for(f=oo, x=t; x!=s; f=min(f, e[p[x]].cap), x=e[p[x]^1].to);
for(r+=f, x=t; x!=s; e[p[x]].cap-=f, e[p[x]^1].cap+=f, x=e[p[x]^1].to);
}
}
else {
if(!--gap[d[x]]) {
break;
}
d[x]=n;
for(i=ihead[x]; i; i=e[i].next) {
if(e[i].cap && d[x]>d[e[i].to]+1) {
d[x]=d[e[i].to]+1;
cur[x]=i;
}
}
++gap[d[x]];
if(x!=s) {
x=e[p[x]^1].to;
}
}
}
return r;
}
int n, m, s, t;
bool check(int mid) {
static int rest[N], match[N];
fill(rest+1, rest+1+n, mid);
int need=0;
for(int i=1; i<=m; ++i) {
int x=X[i], y=Y[i];
if(rest[x]<rest[y]) {
swap(x, y);
}
if(!rest[x]) {
++need;
match[i]=0;
}
else {
match[i]=x;
--rest[x];
}
}
if(!need) {
return 1;
}
int ct=1;
for(int i=1; i<=m; ++i) {
if(!match[i]) {
e[++ct].cap=1, e[++ct].cap=0;
e[++ct].cap=1, e[++ct].cap=0;
e[++ct].cap=1, e[++ct].cap=0;
}
else {
e[++ct].cap=0, e[++ct].cap=1;
if(X[i]==match[i]) {
e[++ct].cap=0, e[++ct].cap=1;
e[++ct].cap=1, e[++ct].cap=0;
}
else {
e[++ct].cap=1, e[++ct].cap=0;
e[++ct].cap=0, e[++ct].cap=1;
}
}
}
for(int i=1; i<=n; ++i) {
e[++ct].cap=rest[i], e[++ct].cap=mid-rest[i];
}
return isap(s, t, t)==need;
}
int main() {
n=getint(), m=getint(), s=m+n+1, t=s+1;
for(int i=1; i<=m; ++i) {
int x=X[i]=getint(), y=Y[i]=getint();
add(s, i);
add(i, m+x);
add(i, m+y);
if(win[x]>win[y]) {
swap(x, y);
}
++win[x];
}
int l=0, r=0;
for(int i=1; i<=n; ++i) {
add(m+i, t);
r=max(r, win[i]);
}
while(l<=r) {
int mid=(l+r)>>1;
check(mid)?(r=mid-1):(l=mid+1);
}
printf("%d\n", r+1);
return 0;
}