http://www.lydsy.com/JudgeOnline/problem.php?id=1532

题意

n个人，m场比赛，求赢得最多的人最少赢多少场。

题解

二分答案X；

S向每场比赛连边，容量为1；

每场比赛向参赛的两个人连边容量oo；

每个人向T连边，容量为X。

如果答案合法，最大流为m。

sap卡了，不知道为什么在这种二分图上dinic会快

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<climits>
#include<queue>
using namespace std;
const int N=20011,M=5*N;
int u[M],v[M],w[M],next[M],head[N],cur[N],k;
int n,m,a[10001],b[10001];
int s,t,pre[N],low[N],d[N],vd[N];
queue<int> q;
void add(int x,int y,int z)
{
    u[++k]=x;v[k]=y;w[k]=z;next[k]=head[x];head[x]=k;
    u[++k]=y;v[k]=x;w[k]=0;next[k]=head[y];head[y]=k;
}
 
bool bfs()
{
    int now;bool flag=false;
    memset(d,-1,sizeof(d));
    q.push(t);d[t]=0;
    while(!q.empty())
    {
        now=q.front();q.pop();
        for(int i=head[now];i;i=next[i])
            if(d[v[i]]==-1 && w[i^1])
            {
                d[v[i]]=d[now]+1;
                q.push(v[i]);
                if(v[i]==s) flag=true;
            }
    }
    return flag;
}
int dfs(int now,int low)
{
    if(now==t)  return low;
    int ret=low,tmp;
    for(int i=head[now];i;i=next[i])
    {
        if(d[v[i]]!=d[now]-1 || !w[i])  continue;
        tmp=dfs(v[i],min(low,w[i]));
        low-=tmp;
        w[i]-=tmp;w[i^1]+=tmp;
        if(low==0)  break;
    }
    if(low==ret)d[now]=-1;
    return ret-low;
}
int solve()
{
    int ans=0,flow;
    while(bfs())
        while(flow=dfs(s,INT_MAX))
            ans+=flow;
    return ans;
}
void build(int x)
{
    memset(head,0,sizeof(head));k=1;
    for(int i=1;i<=m;i++)
    {
        add(s,i,1);
        add(i,m+a[i],1);add(i,m+b[i],1);
    }
    for(int i=1;i<=n;i++)
        add(m+i,t,x);
}
 
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",a+i,b+i);
    s=n+m+1;t=s+1;
    int l=1,r=m,mid;
    while(l<=r)
    {
        mid=l+r>>1;
        build(mid);
        if(solve()==m)  r=mid-1;
        else    l=mid+1;
    }
    printf("%d\n",l);
}