[CQOI2009]dance跳舞（最大流+二分）

[CQOI2009]dance跳舞

每个人拆成$2$个点，表示是否与喜欢的人跳舞

跳$m$首舞曲时，满足最大流为$n*m$

二分$m$，跑最大流即可

#include<cstdio>

#include<cstring>

inline int min(int A,int B){return A<B?A:B;}

#define W 9999

int n,k,S,T,cur[W],d[W],L,R,h[W];

char q[][]; bool vis[W];

int Cnt,hd[W],nxt[W],ed[W],poi[W],val[W];

void adde(int x,int y,int v){

    nxt[ed[x]]=++Cnt; hd[x]=hd[x]?hd[x]:Cnt;

    ed[x]=Cnt; poi[Cnt]=y; val[Cnt]=v;

}

inline void link(int x,int y,int v){adde(x,y,v),adde(y,x,);}

#define to poi[i]

bool bfs(){

    for(int i=;i<=T;++i) cur[i]=hd[i],vis[i]=;

    h[L=]=S; R=; vis[S]=;

    while(L!=R){

        int x=h[L++]; if(L>=W)L=;

        for(int i=hd[x];i;i=nxt[i])

            if(!vis[to]&&val[i]){

                vis[to]=,d[to]=d[x]+;

                h[R++]=to; if(R>=W)R=;

            }

    }return vis[T];

}

int dfs(int x,int a){

    if(x==T||!a) return a;

    int F=,f;

    for(int &i=cur[x];i;i=nxt[i]){

        if(d[to]==d[x]+&&(f=dfs(to,min(a,val[i])))>)

            F+=f,a-=f,val[i]-=f,val[i^]+=f;

        if(!a) break;

    }return F;

}

int dinic(){int re=; while(bfs())re+=dfs(S,W); return re;}

int chk(int x){

    memset(hd,,sizeof(hd)); Cnt=;

    memset(ed,,sizeof(ed));

    memset(nxt,,sizeof(nxt));

    for(int i=;i<=n;++i) link(S,i,x),link(i+n*,T,x);

    for(int i=;i<=n;++i){

        link(i,i+n,k); link(i+n*,i+n*,k);

        for(int j=;j<=n;++j){

            if(q[i][j]=='Y') link(i,j+n*,);

            else link(i+n,j+n*,);

        }

    }return dinic()==x*n;

}

int main(){

    scanf("%d%d",&n,&k); S=n*+,T=S+;

    for(int i=;i<=n;++i) scanf("%s",q[i]+);

    int l=,r=n+;

    while(l<r){

        int mid=(l+r)/;

        if(chk(mid)) l=mid+;

        else r=mid;

    }printf("%d",l-);

    return ;

}