首页 > 代码库 > BZOJ-1305: [CQOI2009]dance跳舞（最大流 增加超级源汇+分裂点+二分 水题）
BZOJ-1305: [CQOI2009]dance跳舞（最大流 增加超级源汇+分裂点+二分 水题）
1305: [CQOI2009]dance跳舞
Time Limit: 5 Sec Memory Limit: 162 MBDescription
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？
Input
第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为‘Y‘当且仅当男孩i和女孩j相互喜欢。
Output
仅一个数，即舞曲数目的最大值。
Sample Input
3 0
YYY
YYY
YYY
YYY
YYY
YYY
Sample Output
3
HINT
N<=50 K<=30
垃圾网络流1A，增加超级源汇+分裂点+最大流+二分。
男，女各分裂成喜欢yes和不喜欢no两个点
若男女是cp，则每个男yes-->每个女yes 容量1
若男女不是cp，则每个男no-->每个女no 容量1
控制：每个男孩都不会和同一个女孩跳两首（或更多）舞曲。
每个男yes-->自己no 容量k
每个女no-->自己yes 容量k
控制：每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。
最后二分x（暴力枚举ok，数据弱爆了！）
S--->每个男yes 容量x
每个女yes--->T 容量x
若最大流==x*人数（即满流） 则成立。
控制：每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。
ISAP！！！跑的飞快。。。
#include<iostream>#include<fstream>#include<cstdio>#include<algorithm>#include<string>#include<vector>#include<queue>#include<deque>#include<utility>#include<map>#include<set>#include<cmath>#include<cstdlib>#include<ctime>#include<functional>#include<sstream>#include<cstring>#include<bitset>#include<stack>using namespace std;int n,m,s,t,cnt,x,y,z,k,ans;char ss[55][55];struct sdt{ int cap,flow,u,v;}e[200005];int nxt[200005],fir[10005],d[10005],par[10005],num[10005],cur[10005];bool vis[10005];int read(){ int x=0;char c=getchar(); while(c<48||c>57)c=getchar(); while(c>47&&c<58)x*=10,x+=c-48,c=getchar(); return x;}void add(int u,int v,int cp,int fl){ e[++cnt].u=u;e[cnt].v=v;e[cnt].cap=cp;e[cnt].flow=fl; nxt[cnt]=fir[u];fir[u]=cnt;}void bfs(){ memset(vis,0,sizeof(vis)); memset(d,0,sizeof(d)); queue<int>q; d[t]=0; vis[t]=1; q.push(t); while(!q.empty()) { int k=q.front(); q.pop(); for(int i=fir[k];i;i=nxt[i]) { if(!vis[e[i].v] && e[i].cap==0) { vis[e[i].v]=1; d[e[i].v]=d[k]+1; q.push(e[i].v); } } }}int agument(){ int p=t; int ans=2147483647; while(p!=s) { ans=min(ans,e[par[p]].cap-e[par[p]].flow); p=e[par[p]].u; } p=t; while(p!=s) { e[par[p]].flow+=ans; e[par[p]^1].flow-=ans; p=e[par[p]].u; } return ans;}int isap(){ memset(num,0,sizeof(num)); int flow=0; for(int i=1;i<=n;i++) { num[d[i]]++; cur[i]=fir[i]; } int p=s; while(d[s]<n) { if(p==t) { flow+=agument(); p=s; } bool ok=0; for(int i=cur[p];i;i=nxt[i]) { if(e[i].cap>e[i].flow && d[p]==d[e[i].v]+1) { ok=1; par[e[i].v]=i; cur[p]=i; p=e[i].v; break; } } if(!ok) { int mn=n-1; for(int i=fir[p];i;i=nxt[i]) { if(e[i].cap>e[i].flow)mn=min(mn,d[e[i].v]); } if(--num[d[p]]==0)break; num[d[p]=mn+1]++; cur[p]=fir[p]; if(p!=s)p=e[par[p]].u; } } return flow;}void build(int yhy){ memset(nxt,0,sizeof(nxt)); memset(fir,0,sizeof(fir)); cnt=1; for(int i=1;i<=m;i++) { add(1,1+i,yhy,0); add(1+i,1,0,0); add(1+2*m+i,t,yhy,0); add(t,1+2*m+i,0,0); for(int j=0;j<m;j++) { if(ss[i][j]==‘Y‘) { add(1+i,1+2*m+j+1,1,0); add(1+2*m+j+1,i+1,0,0); } else { add(1+m+i,1+3*m+j+1,1,0); add(1+3*m+j+1,1+i+m,0,0); } } add(1+i,1+m+i,k,0); add(1+m+i,1+i,0,0); add(1+3*m+i,1+2*m+i,k,0); add(1+2*m+i,1+3*m+i,0,0); }}int main(){ m=read(); k=read(); n=2+4*m; s=1; t=2+4*m; for(int i=1;i<=m;i++) { for(int j=0;j<m;j++) { cin>>ss[i][j]; } } int l=0,r=m; while(l<=r) { int mid=(l+r)/2; build(mid); bfs(); if(isap()==mid*m) { l=mid+1; ans=mid; } else { r=mid-1; } } printf("%d\n",ans); return 0;}
BZOJ-1305: [CQOI2009]dance跳舞（最大流 增加超级源汇+分裂点+二分 水题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。