bzoj [POI2005]Kos-Dicing 二分+网络流

[POI2005]Kos-Dicing

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1835 Solved: 661
[Submit][Status][Discuss]

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

HINT

一场比赛向x,y各连流量为1的边，然后二分z，所有点向T连z的边，然后最大流一

下，调整一下就好了。

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #define inf 0x7fffffff

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x*=;x+=ch-'';ch=getchar();}

     return x*f;

 }

 int T;

 int n,m,cnt,ans,x[],y[];

 int head[],h[],q[],cur[];

 struct data{int to,next,v;}e[];

 void ins(int u,int v,int w)

 {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}

 void insert(int u,int v,int w)

 {ins(u,v,w);ins(v,u,);}

 bool bfs()

 {

     int t=,w=;

     for(int i=;i<=T;i++)h[i]=-;

     q[]=;h[]=;

     while(t!=w)

     {

         int now=q[t];t++;

         for(int i=head[now];i;i=e[i].next)

             if(e[i].v&&h[e[i].to]==-)

             {

                 h[e[i].to]=h[now]+;

                 q[w++]=e[i].to;

             }

     }

     if(h[T]==-)return ;

     return ;

 }

 int dfs(int x,int f)

 {

     if(x==T)return f;

     int w,used=;

     for(int i=cur[x];i;i=e[i].next)

     {

         if(e[i].v&&h[e[i].to]==h[x]+)

         {

             w=f-used;

             w=dfs(e[i].to,min(e[i].v,w));

             e[i].v-=w;

             if(e[i].v)cur[x]=i;

             e[i^].v+=w;

             used+=w;if(used==f)return f;

         }

     }

     if(!used)h[x]=-;

     return used;

 }

 void dinic()

 {while(bfs()){for(int i=;i<=T;i++)cur[i]=head[i];ans+=dfs(,inf);}}

 void build(int v)

 {

     cnt=;ans=;

     memset(head,,sizeof(head));

     for(int i=;i<=n;i++)

         insert(i,T,v);

     for(int i=;i<=m;i++)

     {

         insert(,i+n,);

         insert(i+n,x[i],);

         insert(i+n,y[i],);

     }

 }

 int main()

 {

     n=read();m=read();T=n+m+;

     for(int i=;i<=m;i++)

         x[i]=read(),y[i]=read();

     int l=,r=;

     while(l<=r)

     {

         int mid=(l+r)>>;

         build(mid);

         dinic();

         if(ans==m)r=mid-;

         else l=mid+;

     }

     printf("%d",l);

 }

秒客网