最大流。
首先二分答案，问题转化为x首舞曲是否可行。
考虑建图，对每个人建立三个点，分别表示全体，喜欢和不喜欢。
源点向每个男生全体点连一条容量为x的边。
每个男生整体点向喜欢点连一条容量为正无穷的边，向不喜欢点连一条容量为k的边。
每个男生喜欢点向所有他喜欢的女生的喜欢点连一条容量为一的边，不喜欢点向所有他不喜欢的女生的不喜欢点连一条容量为一的边。
每个女生喜欢点向整体点连一条容量为正无穷的边，不喜欢点向整体点连一条容量为k的边。
每个女生整体点向汇点连一条容量为x的边。
check即为判断最大流是否等于n*x。
本题中流量的定义为舞曲数，整体点向源汇点的连边保证了每一轮正好配成n对，如某一轮中存在一个女生对应多个男生，最终最大流就会减小。
#include<cstring> #include<cstdio> #include<algorithm> #include<iostream> #include<queue> using namespace std; const int dian=305; const int bian=40005; const int INF=0x3f3f3f3f; int n,k,tot; int S,T; int h[dian],nxt[bian],ver[bian],val[bian],ch[dian]; char map[55][55]; void add(int aa,int bb,int cc){ tot++;ver[tot]=bb;val[tot]=cc;nxt[tot]=h[aa];h[aa]=tot; tot++;ver[tot]=aa;val[tot]=0;nxt[tot]=h[bb];h[bb]=tot; } int bh(int aa,int p,int ok){ return (aa-1)*3+p+ok*3*n; } bool tell(){ memset(ch,-1,sizeof(ch)); queue<int>q; q.push(S); ch[S]=0; while(!q.empty()){ int t=q.front(); q.pop(); for(int i=h[t];i;i=nxt[i]) if(ch[ver[i]]==-1&&val[i]){ q.push(ver[i]); ch[ver[i]]=ch[t]+1; } } return ch[T]!=-1; } int zeng(int a,int b){ if(a==T) return b; int r=0; for(int i=h[a];i&&b>r;i=nxt[i]) if(ch[ver[i]]==ch[a]+1&&val[i]){ int t=zeng(ver[i],min(b-r,val[i])); val[i]-=t,r+=t,val[i^1]+=t; } if(!r) ch[a]=-1; return r; } int dinic(){ int r=0,t; while(tell()) while(t=zeng(S,INF)) r+=t; return r; } bool check(int mid){ memset(nxt,0,sizeof(nxt)); memset(h,0,sizeof(h)); tot=1; for(int i=1;i<=n;i++){ add(S,bh(i,1,0),mid); add(bh(i,1,1),T,mid); add(bh(i,1,0),bh(i,2,0),INF); add(bh(i,1,0),bh(i,3,0),k); add(bh(i,2,1),bh(i,1,1),INF); add(bh(i,3,1),bh(i,1,1),k); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(map[i][j]=='Y') add(bh(i,2,0),bh(j,2,1),1); else add(bh(i,3,0),bh(j,3,1),1); } if(dinic()==n*mid) return true; return false; } int bin(int l,int r){ int mid; while(l<r){ mid=(l+r+1)>>1; if(check(mid)) l=mid; else r=mid-1; } return l; } int main(){ scanf("%d%d",&n,&k); S=6*n+1,T=6*n+2; for(int i=1;i<=n;i++) scanf("%s",map[i]+1); printf("%d",bin(0,50)); return 0; }