首页 > 代码库 > BZOJ1532: [POI2005]Kos-Dicing
BZOJ1532: [POI2005]Kos-Dicing
1532: [POI2005]Kos-Dicing
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 1060 Solved: 321
[Submit][Status]
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
神了，网络流还能这么用？
别人的题解：
我们对于每场比赛，有一个点，超级源向每场比赛连一条边，流量为1
View Code
别人的题解：
我们对于每场比赛，有一个点，超级源向每场比赛连一条边，流量为1
然后每场比赛向对应的两个人连一条边，流量均为1（其实无所谓）
每个人向超级汇连一条边，容量为x
x实际上就是限制了每个人能够赢的次数，也就是最大值
因为最大值有多个是合法的，全部都达到这个最大值也无所谓
那么我们二分这个x
对建出来的图跑一遍网络流
网络流将会自动分配流量
如果x不合法，也就是如果存在有人必须赢大于x次，那么最大流将会小于m
数据范围有点儿坑爹。。。
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 150000 26 27 #define maxm 150000 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 using namespace std; 44 45 inline int read() 46 47 { 48 49 int x=0,f=1;char ch=getchar(); 50 51 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 52 53 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 54 55 return x*f; 56 57 } 58 int n,m,s,t,maxflow,tot=1,a[maxn],b[maxn],head[maxn],cur[maxn],h[maxn],q[maxn]; 59 60 struct edge{int go,next,v;}e[maxm]; 61 62 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;} 63 64 void insert(int x,int y,int z){ins(x,y,z);ins(y,x,0);} 65 66 bool bfs() 67 68 { 69 70 for(int i=s;i<=t;i++)h[i]=-1; 71 72 int l=0,r=1;q[1]=s;h[s]=0; 73 74 while(l<r) 75 76 { 77 78 int x=q[++l]; 79 80 for(int i=head[x];i;i=e[i].next) 81 82 if(e[i].v&&h[e[i].go]==-1) 83 84 { 85 86 h[e[i].go]=h[x]+1;q[++r]=e[i].go; 87 88 } 89 90 } 91 92 return h[t]!=-1; 93 94 } 95 96 int dfs(int x,int f) 97 98 { 99 100 if(x==t) return f;101 102 int tmp,used=0;103 104 for(int i=head[x];i;i=e[i].next)105 106 if(e[i].v&&h[e[i].go]==h[x]+1)107 108 {109 110 tmp=dfs(e[i].go,min(e[i].v,f-used));111 112 e[i].v-=tmp;if(e[i].v)cur[x]=i;113 114 e[i^1].v+=tmp;used+=tmp;115 116 if(used==f)return f; 117 118 }119 120 if(!used) h[x]=-1;121 122 return used;123 124 }125 126 void dinic()127 128 {129 130 maxflow=0;131 132 while(bfs())133 134 {135 136 for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf);137 138 }139 140 }141 inline bool check(int x)142 {143 memset(head,0,sizeof(head));tot=1;s=0;t=n+m+1;144 for1(i,m)145 {146 insert(s,i,1);147 insert(i,m+a[i],1);insert(i,m+b[i],1);148 }149 for1(i,n)insert(m+i,t,x);150 dinic();151 return maxflow==m;152 } 153 154 int main()155 156 {157 158 freopen("input.txt","r",stdin);159 160 freopen("output.txt","w",stdout);161 162 n=read();m=read();163 for1(i,m)a[i]=read(),b[i]=read();164 int l=1,r=m,mid;165 while(l<=r)166 {167 mid=(l+r)>>1;168 if(check(mid))r=mid-1;else l=mid+1;169 }170 printf("%d\n",l); 171 172 return 0;173 174 }
BZOJ1532: [POI2005]Kos-Dicing
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。