1532: [POI2005]Kos-Dicing
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1520 Solved: 516[][][]Description
Dicing 是一个两人玩的游戏,这个游戏在Byteotia非常流行. 甚至人们专门成立了这个游戏的一个俱乐部. 俱乐部的人时常在一起玩这个游戏然后评选出玩得最好的人.现在有一个非常不走运的家伙,他想成为那个玩的最好的人,他现在知道了所有比赛的安排,他想知道,在最好的情况下,他最少只需要赢几场就可以赢得冠军,即他想知道比赛以后赢的最多的那个家伙最少会赢多少场.
Input
第一行两个整数n 和 m, 1 <= n <= 10 000, 0 <= m <= 10 000; n 表示一共有多少个参赛者, m 表示有多少场比赛. 选手从1 到 n编号. 接下来m 行每行两个整数表示该场比赛的两个选手,两个选手可能比赛多场.
Output
第一行表示赢得最多的人最少会赢多少场
Sample Input
4 4 1 2 1 3 1 4 1 2
Sample Output
1
HINT
一开始没看出是流 【墙角熊】
二分答案x
S向每个人连x
每个人向参加的比赛连
比赛向T连
判断最大流是否等于比赛数
1 #include2 #define inf 2147483647 3 #define N 20233 4 #define rep(i,l,r) for(int i=l;i<=r;i++) 5 using namespace std; 6 7 int head[N],tot,n,m,T,dis[N],a[N],b[N]; 8 struct node{ 9 int to,next,w;10 }e[1023333];11 inline bool bfs(){12 for(int i=0;i<=T;i++) dis[i]=-1; queue q; q.push(0); dis[0]=0;13 while(!q.empty()) {14 int x=q.front(); q.pop();15 for(int k=head[x];k;k=e[k].next) 16 if(dis[e[k].to]<0 && e[k].w>0) {17 dis[e[k].to]=dis[x]+1; q.push(e[k].to);18 }19 }20 if(dis[T]>0) return 1;else return 0;21 }22 int find(int x,int low){23 if(x==T) return low;24 int delta=low,now;25 for(int k=head[x];k;k=e[k].next) 26 if(e[k].w>0 && dis[e[k].to]==dis[x]+1){ 27 now=find(e[k].to,min(e[k].w,delta));28 e[k].w-=now; e[k^1].w+=now; delta-=now;29 if(!delta) return low;30 } 31 dis[x]=-1;32 return low-delta;33 }34 inline void ins(int u,int v,int w) {35 e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w;36 }37 inline void insert(int u,int v,int w) {38 ins(u,v,w); ins(v,u,0);39 }40 int main () {41 scanf("%d%d",&n,&m);42 rep(i,1,m) scanf("%d%d",&a[i],&b[i]);43 int l,r,ans,mid,sum;44 l=1,r=m,mid,ans=m,T=n+m+1;45 while(l<=r) {46 mid=(l+r)>>1;47 memset(head,0,sizeof(head)); tot=1; sum=0;48 rep(i,1,n) insert(i+m,T,mid);49 rep(i,1,m) insert(0,i,1),insert(i,m+a[i],1),insert(i,m+b[i],1);50 while(bfs()) sum+=find(0,inf);51 if(sum==m) ans=min(ans,mid),r=mid-1;else l=mid+1;52 }53 printf("%d\n",ans);54 }
