Bzoj 1532: [POI2005]Kos-Dicing 二分,网络流

2022-11-04 08:34:47

1532: [POI2005]Kos-Dicing

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1373 Solved: 444
[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

Source

题解：

二分＋网络流。

S向每场比赛连边为1，每场比赛向两个选手连边为1，每个选手向T连二分的上界cap即可。

 #include<bits/stdc++.h>

 using namespace std;

 #define MAXN 20020

 #define INF 1e9

 struct node

 {

     int begin,end,value,next;

 }edge[*MAXN];

 int cnt,Head[MAXN],S,T,dis[MAXN],q[MAXN],a[MAXN],b[MAXN],n,m,cur[MAXN];

 void addedge(int bb,int ee,int vv)

 {

     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].value=vv;edge[cnt].next=Head[bb];Head[bb]=cnt;

 }

 void addedge1(int bb,int ee,int vv)

 {

     addedge(bb,ee,vv);addedge(ee,bb,vv);

 }

 int read()

 {

     int s=,fh=;char ch=getchar();

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

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

     return s*fh;

 }

 void Build(int cap)

 {

     memset(Head,-,sizeof(Head));cnt=;

     for(int i=;i<=m;i++){addedge1(S,n+i,);addedge1(n+i,a[i],);addedge1(n+i,b[i],);}

     for(int i=;i<=n;i++)addedge1(i,T,cap);

 }

 int BFS()

 {

     int head,tail,u,v,i;

     head=;tail=;q[tail]=S;

     memset(dis,-,sizeof(dis));dis[S]=;

     while(head!=tail)

     {

         head++;if(head==)head=;

         u=q[head];

         for(i=Head[u];i!=-;i=edge[i].next)

         {

             v=edge[i].end;

             if(edge[i].value>&&dis[v]<)

             {

                 dis[v]=dis[u]+;

                 tail++;if(tail==)tail=;

                 q[tail]=v;

             }

         }

     }

     if(dis[T]<=)return ;

     else return ;

 }

 int DFS(int u,int minflow)

 {

     int used=,ans=,i,v;

     if(u==T)return minflow;

     for(i=Head[u];i!=-;i=edge[i].next)

     {

         v=edge[i].end;

         if(edge[i].value>&&dis[v]==dis[u]+)

         {

             ans=minflow-used;

             ans=DFS(v,min(ans,edge[i].value));

             edge[i].value-=ans;

             edge[i^].value+=ans;

             used+=ans;

             if(used==minflow)return minflow;

         }

     }

     if(used==)dis[u]=-;

     return used;

 }

 int Dinic()

 {

     int maxflow=,ans=,i;

     while(BFS()){for(i=;i<=T;i++)cur[i]=Head[i];ans=DFS(S,INF);if(ans==)break;maxflow+=ans;}

     return maxflow;

 }

 int main()

 {

     int i,l,r,mid,k,ans=;

     n=read();m=read();

     S=n+m+;T=S+;

     //memset(Head,-1,sizeof(Head));cnt=1;

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

     {

         //addedge1(S,n+i,1);

         a[i]=read();b[i]=read();

         //addedge1(n+i,a,INF);

         //addedge1(n+i,b,INF);

     }

     //cntcnt=cnt;

     l=;r=m;

     while(l<=r)

     {

         mid=(l+r)/;

         Build(mid);

         k=Dinic();

         if(k>=m){ans=mid;r=mid-;}

         else l=mid+;

     }

     printf("%d",ans);

     return ;

 }

码农公寓