首页 > 代码库 > bzoj 1305: [CQOI2009]dance 二分+網絡流判定
bzoj 1305: [CQOI2009]dance 二分+網絡流判定
1305: [CQOI2009]dance跳舞
Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 1340 Solved: 581
[Submit][Status]
Description
一次舞会有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
Source
加强数据By dwellings and liyizhen2
這道題知道是二分+網絡流後，就是完完全全的水題了。
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<ctime>#include<cmath>#include<algorithm>#include<set>#include<map>#include<vector>#include<string>#include<queue>using namespace std;#ifdef WIN32#define LL "%I64d"#else#define LL "%lld"#endif#define MAXN 55#define MAXV MAXN*MAXN*2#define MAXE MAXV*2#define INF 0x3f3f3f3f#define INFL 0x3f3f3f3f3f3f3f3fLLtypedef long long qword;inline int nextInt(){ char ch; int x=0; bool flag=false; do ch=getchar(),flag=(ch==‘-‘)?true:flag; while(ch<‘0‘||ch>‘9‘); do x=x*10+ch-‘0‘; while (ch=getchar(),ch<=‘9‘ && ch>=‘0‘); return x*(flag?-1:1);}int n,m;char mp[MAXN][MAXN];struct Edge{ int val,np; Edge *next,*neg;}E[MAXE],*V[MAXV];int tope=1;int sour=0,sink=1;inline void addedge(int x,int y,int z){ //cout<<"Add edge:<"<<tope+1<<">"<<x<<" "<<y<<":"<<z<<endl; E[++tope].np=y; E[tope].val=z; E[tope].next=V[x]; V[x]=&E[tope]; E[++tope].np=x; E[tope].val=0; E[tope].next=V[y]; V[y]=&E[tope]; E[tope].neg=&E[tope-1]; E[tope-1].neg=&E[tope];}int q[MAXV],lev[MAXV];int vis[MAXV],bfstime=0;bool bfs(){ int i,j; int head=-1,tail=0; Edge *ne; lev[sour]=1; vis[sour]=++bfstime; q[0]=sour; while (head<tail) { for (ne=V[q[++head]];ne;ne=ne->next) { if (!ne->val || vis[ne->np]==bfstime)continue; q[++tail]=ne->np; vis[ne->np]=bfstime; lev[ne->np]=lev[q[head]]+1; } } return vis[sink]==bfstime;}int dfs(int now,int maxf){ int ret=0,t; if (now==sink || !maxf)return maxf; Edge* ne; for (ne=V[now];ne;ne=ne->next) { if (!ne->val || lev[ne->np]!=lev[now]+1)continue; t=dfs(ne->np,min(maxf,ne->val)); ne->val-=t; ne->neg->val+=t; maxf-=t; ret+=t; //cout<<"Flow:"<<now<<"-"<<ne->np<<":"<<x<<"("<<ne->val<<")"<<endl; } if (!ret)lev[now]=-1; return ret;}int dinic(){ int ret=0; while (bfs()) { ret+=dfs(sour,INF); } return ret;}int main(){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int i,j,k; int x,y,z; scanf("%d%d\n",&n,&m); for (i=0;i<n;i++) { fgets(mp[i],MAXN,stdin); } int ans=0; int l=0,r=n+1,mid; while (l+1<r) { memset(V,0,sizeof(V)); tope=-1; mid=(l+r)>>1; for (i=0;i<n;i++) { addedge(sour,2+i,mid); addedge(2+i,2+i+n*2,m); addedge(2+i+n,sink,mid); addedge(2+i+n+n*2,2+i+n,m); } for (i=0;i<n;i++) { for (j=0;j<n;j++) { if (mp[i][j]!=‘Y‘) { addedge(2+i+n*2,2+n+j+n*2,1); }else { addedge(2+i,2+j+n,1); } } } ans=dinic(); if (ans!=mid*n) { r=mid; }else { l=mid; } } printf("%d\n",l); return 0;}
bzoj 1305: [CQOI2009]dance 二分+網絡流判定
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。