1305: [CQOI2009]dance跳舞
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 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 0x3f3f3f3f3f3f3f3fLL
typedef long long qword;
inline int nextInt()
{
char ch;
int x=;
bool flag=false;
do
ch=getchar(),flag=(ch=='-')?true:flag;
while(ch<''||ch>'');
do x=x*+ch-'';
while (ch=getchar(),ch<='' && ch>='');
return x*(flag?-:);
} int n,m; char mp[MAXN][MAXN];
struct Edge
{
int val,np;
Edge *next,*neg;
}E[MAXE],*V[MAXV];
int tope=;
int sour=,sink=;
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=;
E[tope].next=V[y];
V[y]=&E[tope]; E[tope].neg=&E[tope-];
E[tope-].neg=&E[tope];
}
int q[MAXV],lev[MAXV];
int vis[MAXV],bfstime=;
bool bfs()
{
int i,j;
int head=-,tail=;
Edge *ne;
lev[sour]=;
vis[sour]=++bfstime;
q[]=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]]+;
}
}
return vis[sink]==bfstime;
}
int dfs(int now,int maxf)
{
int ret=,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]+)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]=-;
return ret;
}
int dinic()
{
int ret=;
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=;i<n;i++)
{
fgets(mp[i],MAXN,stdin);
}
int ans=;
int l=,r=n+,mid;
while (l+<r)
{
memset(V,,sizeof(V));
tope=-;
mid=(l+r)>>;
for (i=;i<n;i++)
{
addedge(sour,+i,mid);
addedge(+i,+i+n*,m);
addedge(+i+n,sink,mid);
addedge(+i+n+n*,+i+n,m);
}
for (i=;i<n;i++)
{
for (j=;j<n;j++)
{
if (mp[i][j]!='Y')
{
addedge(+i+n*,+n+j+n*,);
}else
{
addedge(+i,+j+n,);
}
}
}
ans=dinic();
if (ans!=mid*n)
{
r=mid;
}else
{
l=mid;
}
}
printf("%d\n",l);
return ;
}