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
1 2
1 3
1 4
1 2
Sample Output
1
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 ;
}