Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 4169 Solved: 1804
[Submit][Status][Discuss]
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
乍一看以为多重二分图匹配，花了半个小时写出来82分WA了，搜一遍题解才知道是网络流最大流拆点
将所有人拆为两个点，男生为xi，xj，女生为yi，yj
将相互喜欢的人，由xi连向yi，容量为1
将互相不喜欢的人，由xj连向yj，容量为1
将所有男生的xi连向xj，容量为k
将所有女生yj连向yi，容量为k
将源点连向xi，容量为a
yi连向汇点，容量为a
二分法枚举容量a，计算最大流，若flow<n*a，即无法满流，则停止二分
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; const int INF=0x7f7f7f7f;
const int MAXN=; struct Edge
{
int to,w,next;
}E[MAXN];
int node=,head[MAXN],dis[MAXN];
int s=,t=;
int n,k,ans;
bool mp[][]; void insert(int u,int v,int w)
{
E[++node]=(Edge){v,w,head[u]};
head[u]=node;
E[++node]=(Edge){u,,head[v]};
head[v]=node;
} bool bfs()
{
memset(dis,-,sizeof(dis));
queue<int> Q;
Q.push(s);
dis[s]=;
while(!Q.empty())
{
int q=Q.front();Q.pop();
for(int i=head[q];i;i=E[i].next)
if(E[i].w&&dis[E[i].to]==-)
{
Q.push(E[i].to);
dis[E[i].to]=dis[q]+;
}
}
return dis[t]!=-;
} int dfs(int x,int flow)
{
if(x==t) return flow;
int w,used=;
for(int i=head[x];i;i=E[i].next)
if(E[i].w&&dis[E[i].to]==dis[x]+)
{
w=flow-used;
w=dfs(E[i].to,min(w,E[i].w));
E[i].w-=w;
E[i^].w+=w;
used+=w;
if(used==flow)return flow;
}
if(!used) dis[x]=-;
return used;
} void dinic()
{
while(bfs()) ans+=dfs(s,INF);
} int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
char ch[];
scanf("%s",ch);
for(int j=;j<=n;j++)
if(ch[j-]=='Y') mp[i][j]=;
}
int left=,right=;
while(left<=right)
{
int mid=(left+right)>>;
node=;memset(head,,sizeof(head));
for(int i=;i<=n;i++)
{
insert(,i,mid);
insert(i,i+,k);
insert(n+i+,n+i,k);
insert(n+i,t,mid);
for(int j=;j<=n;j++)
if(mp[i][j]) insert(i,j+n,);
else insert(i+,j+n+,);
}
ans=;dinic();
if(ans>=n*mid) left=mid+;
else right=mid-;
}
printf("%d",left-);
return ;
}