【传送门：BZOJ1532】
简要题意：
有n个人，m场比赛，求出赢得最多的人最少要赢多少场
题解：
网络流水题
二分答案x，st向每个人连边，流量为x，每个人向关于自己的比赛连边，流量为1，每场比赛向ed连边，流量为1
如果最大流为m，说明答案合法
参考代码：
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<queue> using namespace std; struct node { int x,y,c,next; }a[110000];int len,last[21000]; void ins(int x,int y,int c) { len++; a[len].x=x;a[len].y=y;a[len].c=c; a[len].next=last[x];last[x]=len; len++; a[len].x=y;a[len].y=x;a[len].c=0; a[len].next=last[y];last[y]=len; } queue<int> q; int h[21000],st,ed; bool bt_h() { memset(h,0,sizeof(h)); h[st]=1; q.push(st); while(q.empty()==0) { int x=q.front();q.pop(); for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==0&&a[k].c>0) { h[y]=h[x]+1; q.push(y); } } } if(h[ed]>0) return true; else return false; } int findflow(int x,int f) { if(x==ed) return f; int s=0,t; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(h[y]==h[x]+1&&a[k].c>0&&f>s) { t=findflow(y,min(a[k].c,f-s)); s+=t; a[k].c-=t;a[k^1].c+=t; } } if(s==0) h[x]=0; return s; } struct edge { int x,y; }e[11000];int n,m; bool check(int x) { len=1;memset(last,0,sizeof(last)); st=0;ed=n+m+1; for(int i=1;i<=n;i++) ins(st,i,x); for(int i=1;i<=m;i++) { ins(e[i].x,i+n,1); ins(e[i].y,i+n,1); ins(i+n,ed,1); } int ans=0; while(bt_h()) ans+=findflow(st,1<<30); if(ans==m) return true; else return false; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d",&e[i].x,&e[i].y); int l=0,r=10000,ans; while(l<=r) { int mid=(l+r)/2; if(check(mid)==true) r=mid-1,ans=mid; else l=mid+1; } printf("%d ",ans); return 0; }