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

1

HINT

 

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

下，调整一下就好了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #define inf 0x7fffffff
 6 using namespace std;
 7 inline int read()
 8 {
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
12     return x*f;
13 }
14 int T;
15 int n,m,cnt,ans,x[10005],y[10005];
16 int head[20005],h[20005],q[20005],cur[20005];
17 struct data{int to,next,v;}e[100001];
18 void ins(int u,int v,int w)
19 {e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
20 void insert(int u,int v,int w)
21 {ins(u,v,w);ins(v,u,0);}
22 bool bfs()
23 {
24     int t=0,w=1;
25     for(int i=0;i<=T;i++)h[i]=-1;
26     q[0]=0;h[0]=0;
27     while(t!=w)
28     {
29         int now=q[t];t++;
30         for(int i=head[now];i;i=e[i].next)
31             if(e[i].v&&h[e[i].to]==-1)
32             {
33                 h[e[i].to]=h[now]+1;
34                 q[w++]=e[i].to;
35             }
36     }
37     if(h[T]==-1)return 0;
38     return 1;
39 }
40 int dfs(int x,int f)
41 {
42     if(x==T)return f;
43     int w,used=0;
44     for(int i=cur[x];i;i=e[i].next)
45     {
46         if(e[i].v&&h[e[i].to]==h[x]+1)
47         {
48             w=f-used;
49             w=dfs(e[i].to,min(e[i].v,w));
50             e[i].v-=w;
51             if(e[i].v)cur[x]=i;
52             e[i^1].v+=w;
53             used+=w;if(used==f)return f;
54         }
55     }
56     if(!used)h[x]=-1;
57     return used;
58 }
59 void dinic()
60 {while(bfs()){for(int i=0;i<=T;i++)cur[i]=head[i];ans+=dfs(0,inf);}}
61 void build(int v)
62 {
63     cnt=1;ans=0;
64     memset(head,0,sizeof(head));
65     for(int i=1;i<=n;i++)
66         insert(i,T,v);
67     for(int i=1;i<=m;i++)
68     {
69         insert(0,i+n,1);
70         insert(i+n,x[i],1);
71         insert(i+n,y[i],1);
72     }
73 }
74 int main()
75 {
76     n=read();m=read();T=n+m+1;
77     for(int i=1;i<=m;i++)
78         x[i]=read(),y[i]=read();
79     int l=0,r=5000;
80     while(l<=r)
81     {
82         int mid=(l+r)>>1;
83         build(mid);
84         dinic();
85         if(ans==m)r=mid-1;
86         else l=mid+1;
87     }
88     printf("%d",l);
89 }