这题比较显然的网络流 先考虑建图： 男生向他的镜像节点连一条容量为 k 的边。 女生的镜像节点向她连一条容量为k的边。 男生节点向每一个喜欢的女生连一条容量为 1 的边。 男生镜像向不喜欢的女生镜像连一条容量为1的边。 S向每个男生节点连一条容量待定的边。 每个女生节点向T连一条容量相同的边。 两种方法： 二分答案 mid ，设置源汇连边容量为 mid ，跑最大流，如果 flowmax=mid∗n ，则 ans≥mid 。 每次跑容量为1的最大流，如果 flowmax=n ，就给每条源汇连边扩容，再在残余网络上继续跑最大流，直到流不满。
#include <bits/stdc++.h> #define gc getchar() #define ll long long #define mid (l+r>>1) #define N 59 #define inf 0x3f3f3f3f using namespace std; int n,k,number=1,pos,cur[N<<3],dis[N<<3]; bool vis[N<<3]; vector<int> G[N<<3]; struct edge { int from,to,flow,cap; int rest() { return cap-flow; } void add(int x,int y,int z) { from=x,to=y,cap=z,flow=0; } }e[N*N<<3]; int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0'; return s*x; } void add(int x,int y,int z) { e[++number].add(x,y,z); G[x].push_back(number); e[++number].add(y,x,0); G[y].push_back(number); } #define E e[G[x][i]] bool bfs(int s,int t) { memset(vis,0,sizeof(vis)); queue<int> Q; Q.push(s); dis[s]=0; vis[s]=1; while (!Q.empty()) { int x=Q.front(); Q.pop(); for (int i=0;i<(int)G[x].size();i++) if (!vis[E.to]&&E.rest()>0) { vis[E.to]=1; dis[E.to]=dis[x]+1; Q.push(E.to); } } return vis[t]; } int dfs(int x,int a,int t) { if (x==t||a==0) return a; int flow=0,f; for (int &i=cur[x];i<(int)G[x].size();i++) if (dis[x]+1==dis[E.to]&&(f=dfs(E.to,min(a,E.rest()),t))>0) { E.flow+=f; e[G[x][i]^1].flow-=f; flow+=f; a-=f; if (!a) break; } return flow; } int Maxflow(int s,int t) { int flow=0; while (bfs(s,t)) { memset(cur,0,sizeof(cur)); flow+=dfs(s,inf,t); } return flow; } #undef E bool check(int x) { for (int i=1;i<=number;i++) e[i].flow=0; for (int i=pos+1;i<=number;i++) e[i].cap=((i-pos)&1)?x:0; int tmp=Maxflow(0,4*n+1); return tmp==x*n; } int main() { n=read(),k=read(); for (int i=1;i<=n;i++) add(i,n*2+i,k),add(n*3+i,n+i,k); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) { char ch; while (ch=gc,ch!='Y'&&ch!='N'); if (ch=='Y') add(i,n+j,1); else add(n*2+i,n*3+j,1); } pos=number; for (int i=1;i<=n;i++) add(0,i,0); for (int i=1;i<=n;i++) add(n+i,n*4+1,0); int l=1,r=n,ans=0; while (l<=r) { if (check(mid)) ans=mid,l=mid+1; else r=mid-1; } printf("%d\n",ans); return 0; }