传送门:

BZOJ

洛谷


Description

一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息,舞会最多能有几首舞曲?


Input

第一行包含两个整数nk。以下n行每行包含n个字符,其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。

Output

仅一个数,即舞曲数目的最大值。


Sample Input

3 0
YYY
YYY
YYY

Sample Output

3

HINT

N \le 50,K \le 30


解题思路:

这类题目用二分已经是套路了吧…

然后因为喜欢和不喜欢是有区分的,所以我们将一个人分成喜欢和不喜欢两种来处理。

我们首先二分一个舞曲数目x,由S向代表男生喜欢的部分的点连一条容量为x的边,由女生喜欢部分向T连一条容量为x的边,然后喜欢和不喜欢之间连容量为k的边,男女之间详细的关系就按照给定的一个一个连就好了。

Code:

/*Program from Luvwgyx*/
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=1e9;
const int maxn=3e2+10;
const int maxm=1e5+10;
queue<int >q;char s[maxn][maxn];
struct node{int to,nxt,w;}e[maxm<<1];
int n,k,S,T,tot,maxflow,head[maxn],d[maxn];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}
void write(int x){print(x);puts("");}
void add(int u,int v,int w){
    e[++tot].to=v;e[tot].w=w;e[tot].nxt=head[u];head[u]=tot;
    e[++tot].to=u;e[tot].w=0;e[tot].nxt=head[v];head[v]=tot;
}
bool bfs(){
    memset(d,0,sizeof(d));
    while(!q.empty())q.pop();
    q.push(S);d[S]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
            if(e[i].w&&!d[v]){
                q.push(v);d[v]=d[x]+1;
                if(v==T)return 1;
            }
    }return 0;
}
int dinic(int x,int flow){
    if(x==T)return flow;
    int rest=flow,w;
    for(int i=head[x],v=e[i].to;i&&rest;i=e[i].nxt,v=e[i].to)
        if(e[i].w&&d[v]==d[x]+1){
            w=dinic(v,min(rest,e[i].w));
            if(!w)d[v]=0;
            e[i].w-=w;e[i^1].w+=w;rest-=w;
        }
    return flow-rest;
}
void insert(int x){
    tot=1;maxflow=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=n;i++){
        add(S,i,x);add(i+2*n,T,x);
        add(i,i+n,k);add(i+3*n,i+2*n,k);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(s[i][j]=='Y')add(i,j+2*n,1);
            else add(i+n,j+3*n,1);
        }
    while(bfs())maxflow+=dinic(S,inf);
}
int main(){
    n=read();k=read();S=0;T=4*n+1;
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    int l=0,r=n;
    while(l<=r){
        int mid=(l+r)>>1;insert(mid);
        if(maxflow==mid*n)l=mid+1;
        else r=mid-1;
    }insert(r);
    write(maxflow==r*n?r:l);
    return 0;
}