原来网络流也能二分，今天终于见识了。。。
二分+最大流
题目大意：给定n个人m场比赛，问赢的最多的人最少赢几场
二分答案，增加源汇点，左边一排是比赛点，右边是球员，若有比赛，比赛向俩球员连容量为1的边
源点向比赛连容量为1的边，球员向汇点连容量为二分枚举值的边，判断是最大流是否等于比赛个数
网络流的构图真是个神奇的东西，我承认如果不看网上的解题报告，我真的很难想到，首先是题意不太明确，刚开始我还以为赢的最多的选手胜利的场次必须是最多的。。。但是从样例来看，貌似就算每个人都赢一场也会有冠军出现。。。说说我的理解吧，从超级源点引一条边至代表每场比赛的节点，限制每场比赛的胜利者只有一个人，这个流量如果在射出到某个选手的一条边中，代表这场比赛是他取胜。每个选手到汇点连一条二分枚举的边，就是限制胜利场次的上界，如果最后的最大流等于m,说明这m场比赛的的胜者可以合理的分配，如果不能，说明比赛不能正常进行。又可以分析得出，如果某一个二分值mid满足要求，那么比他大的值一定也满足要求。故可二分枚举答案。（PS:这题的复杂度应该是(10000+10000+2)^2*(m*2+m+n)*log 10000.总觉得要超时啊。。。难道数据弱了？）
int n,m;
struct node2
{
int a,b;
}re[100000];
bool check(int n,int m,int mid)
{
int i;
for(i=0;i<n+m+2;i++)
adj[i]=NULL;
len=0;
int s=n+m;
int t=s+1;
for(i=0;i<m;i++)
insert(s,i,1);
for(i=0;i<n;i++)
insert(m+i,t,mid);
for(i=0;i<m;i++)
{
insert(i,m+re[i].a,1);
insert(i,m+re[i].b,1);
}
return dinic(t+1,s,t)==m;
}
int main()
{
int i;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=0;i<m;i++)
{
scanf("%d%d",&re[i].a,&re[i].b);
re[i].a--;
re[i].b--;
}
int l=1,r=m;
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(n,m,mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}