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
这个题思路很妙啊……第一次做到在网络流中使用二分的题目
其实一开始想到用二分限制的，不过并没有深入思考下去
而是写了一个别人几行就能实现我却用网络流实现的贪心
正解是拆点加二分。
因为答案满足单调性，若可以跳x首曲子，则x-1首肯定也是可以的
建图？
将每个男生和女生拆成两个点：Yes和No
超级源点连接男生的Yes，超级汇点连接女生的Yes
容量设置为二分的x。若跑出来最大流是x*n，就说明满流了
满流即为可以满足x首曲子
对于互相喜欢的，我们在男女的两个Yes点间连边
不喜欢的，我们就在男女的两个No点间连边
那么如何限制k呢？
每个男Yes连自己的No，容量为k
每个女No连自己Yes，容量为k
这样就可以保证k了
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define MAXM (100000+10)
#define MAXN (10000+10)
using namespace std; struct node
{
int Flow;
int next;
int to;
}edge[MAXM*];
int Depth[MAXN],q[MAXN];
int head[MAXN],num_edge;
int n,m,k,s,e,d,INF;
int a[][];
char ch[]; void add(int u,int v,int l)
{
edge[++num_edge].to=v;
edge[num_edge].Flow=l;
edge[num_edge].next=head[u];
head[u]=num_edge;
} bool Bfs(int s,int e)
{
int Head=,Tail=;
memset(Depth,,sizeof(Depth));
Depth[s]=;
q[]=s;
while (Head<Tail)
{
++Head;
int x=q[Head];
for (int i=head[x];i!=;i=edge[i].next)
if (!Depth[edge[i].to] && edge[i].Flow>)
{
Depth[edge[i].to]=Depth[x]+;
q[++Tail]=edge[i].to;
}
}
if (Depth[e]>) return true;
return false;
} int Dfs(int x,int low)
{
int Min,f=;
if (x==e || low==)
return low;
for (int i=head[x];i!=;i=edge[i].next)
if (edge[i].Flow> && Depth[edge[i].to]==Depth[x]+ && (Min=Dfs(edge[i].to , min(low,edge[i].Flow) )))
{
edge[i].Flow-=Min;
edge[((i-)^)+].Flow+=Min;
f+=Min;
low-=Min;
}
return f;
} int Dinic(int s,int e)
{
int Ans=;
while (Bfs(s,e))
Ans+=Dfs(s,0x7fffffff);
return Ans;
} void Addline(int x)
{
memset(head,,sizeof(head));
memset(edge,,sizeof(edge));
num_edge=;
for (int i=;i<=n;++i)
{
add(,i+,x);
add(i+,,);//超级源点 add(i+n+,,x);//超级汇点
add(,i+n+,); add(i+,i+,k);
add(i+,i+,); add(i+n+,i+n+,k);
add(i+n+,i+n+,);
}
for (int i=;i<=n;++i)
{
for (int j=;j<=n;++j)
if (a[i][j]==)
{
add(i+,j+n+,);
add(j+n+,i+,);
}
else
{
add(i+,j+n+,);
add(j+n+,i+,);
}
}
} int main()
{
s=,e=;
memset(&INF,0x7f,sizeof(INF));
scanf("%d%d",&n,&k);
for (int i=;i<=n;++i)
{
scanf("%s",ch);
for (int j=;j<=n;++j)
a[i][j]=(ch[j-]=='Y');
}
int l=,r=n*n;
while (l<r)
{
int mid=(l+r+)/;
Addline(mid);
int Max=Dinic(,);
if (Max==mid*n)
l=mid;
else
r=mid-;
}
printf("%d",l);
}