1305: [CQOI2009]dance跳舞
题目：传送门
题解：
一眼网络流基础建模...然后就GG了
二分答案+拆点建边+最大流判断：
把男女生拆为男1，男2，女1，女2
1、男1和男2还有女1和女2之间连边，流量为约束条件k
2、st连男1，女2连ed，流量为二分的mid
3、如果男生i喜欢女生j，就将男1与女2相连（不在约束条件内）
4、如果不喜欢，就将男2与女1相连（在约束条件内）
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
char ss[][];
struct node
{
int x,y,c,next,other;
}a[];int len,last[];
int st,ed,head,tail,n,k;
void ins(int x,int y,int c)
{
int k1,k2;
k1=++len;
a[len].x=x;a[len].y=y;a[len].c=c;
a[len].next=last[x];last[x]=len; k2=++len;
a[len].x=y;a[len].y=x;a[len].c=;
a[len].next=last[y];last[y]=len; a[k1].other=k2;
a[k2].other=k1;
}
int h[],list[];
bool bt_h()
{
memset(h,,sizeof(h));h[st]=;
head=;tail=;list[]=st;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]== && a[k].c)
{
h[y]=h[x]+;
list[tail++]=y;
}
}
head++;
}
if(h[ed])return true;
return false;
}
int find_flow(int x,int flow)
{
if(x==ed)return flow;
int t,s=;
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y;
if(h[y]==(h[x]+) && a[k].c && s<flow)
{
s+=t=find_flow(y,min(a[k].c,flow-s));
a[k].c-=t;a[a[k].other].c+=t;
}
}
if(s==)h[x]=;
return s;
}
int mid,l,r;
int s1[],s2[];
void build(int cc)
{
len=;memset(last,,sizeof(last));
st=*n+;ed=st+;
for(int i=;i<=n;i++)ins(st,i,cc);
for(int i=;i<=n;i++)ins(i+n*,ed,cc);
for(int i=;i<=n;i++)ins(i,i+*n,k);
for(int i=;i<=n;i++)ins(i+n,i+n*,k);
/*for(int i=1;i<=n;i++)
{
ins(st,i,cc);
ins(i,i+n*2,s1[i]+k);//男1-->男2
}
for(int j=1;j<=n;j++)
{
ins(j+n*3,ed,cc);
ins(j+n,j+n*3,s2[j]+k);//女1-->女2
}*/
for(int i=;i<=n;i++)//男2-->女1
for(int j=;j<=n;j++)
{
if(ss[i][j]=='Y')ins(i,j+n*,);
else ins(i+n*,j+n,);
}
}
bool check(int cnt)
{
build(cnt);
int ans=;
while(bt_h())
ans+=find_flow(st,);
if(ans==n*cnt)return true;
return false;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)scanf("%s",ss[i]+);
l=;r=n;int sum=;
while(l<=r)
{
mid=(l+r)/;
if(check(mid))
{
l=mid+;
sum=mid;
}
else r=mid-;
}
printf("%d\n",sum);
return ;
}