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