题意
一次舞会有 n 个男孩和 n 个女孩。
每首曲子开始时，所有男孩和女孩恰好配成 n 对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。
有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和 k 个不喜欢的女孩跳舞，而每个女孩也最多只愿意和 k 个不喜欢的男孩跳舞。
给出每对男孩女孩是否相互喜欢的信息，求舞会最多能有几首舞曲
思路
考虑将每个男女生拆成两个点，分别为男/女生喜欢/不喜欢。
答案不好求，但由于其满足单调性所以可以使用二分答案，问题变为问跳 a 支舞曲能不能实现，注意到 a 越大越难实现，故单调性得证。
对于每一对互相喜欢的男女，从对应的男生喜欢往女生喜欢连一条容量为 1 的边，对于互相不喜欢的，就从对应的男生不喜欢往女生不喜欢连一条容量为 1 的边。之后建立超级源点 s 和超级汇点 t，从 s 往每个男生喜欢连一条容量为 a 的边（因为最多只能跳 a 支舞曲），从每个女生喜欢往 t 连一条容量为 a 的边，最后再从每个男生喜欢往对应的男生不喜欢连一条容量为 k 的边，从每个女生不喜欢往对应的女生喜欢连一条容量为 k 的边（因为不喜欢的最多只能跳 k 次）
对于每次枚举到的 a，跑一次最大流，如果最大流刚好等于 a\times n，则说明能满足跳 a 支。
具体实现
- 边数组要开够
-
每次枚举到的 a 要重新初始化
剩下的没有什么了，数据范围很小，不加优化的 Dinic 跑得过去
#include <cstdio>
#include <cstring>
#include <queue>
int n,k;
const int maxn=1000;
int head[maxn],cur[maxn],to[maxn<<4],nxt[maxn<<4],c[maxn<<4],cnt;
int dep[maxn];
int s,t;
char tmp[55][55];
inline void add(int u,int v,int w)
{
to[++cnt]=v;
nxt[cnt]=head[u];
c[cnt]=w;
head[u]=cnt;
return;
}
inline int min(int a,int b){return a<b?a:b;}
//男生喜欢 ：1-n 男生不喜欢 n+1-2n 女声喜欢 2n+1-3n 女生不喜欢：3n+1-4n
void build(int a)
{
cnt=1;
memset(head,0,sizeof head);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(tmp[i][j]=='Y')
add(i,2*n+j,1),add(2*n+j,i,0);
else if(tmp[i][j]=='N')
add(n+i,3*n+j,1),add(3*n+j,n+i,0);
}
for(int i=1;i<=n;i++)
add(s,i,a),add(i,s,0),
add(i,n+i,k),add(n+i,i,0),
add(3*n+i,2*n+i,k),add(2*n+i,3*n+i,0),
add(2*n+i,t,a),add(t,2*n+i,0);
}
bool bfs()
{
memset(dep,-1,sizeof dep);
dep[s]=0;
std::queue<int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]>0 && dep[v]==-1)
{
dep[v]=dep[u]+1;
q.push(v);
if(v==t)
return 1;
}
}
}
return 0;
}
int dfs(int u,int sum)
{
if(u==t)
return sum;
int k,res=0;
for(int i=head[u];i && sum;i=nxt[i])
{
int v=to[i];
if(c[i]>0 && dep[v]==dep[u]+1)
{
k=dfs(v,min(sum,c[i]));
if(!k)
dep[v]=-2;
c[i]-=k;
c[i^1]+=k;
res+=k;
sum-=k;
}
}
return res;
}
int dinic()
{
int ret=0;
while(bfs())
ret+=dfs(s,1e9);
return ret;
}
int main()
{
scanf("%d %d",&n,&k);
s=4*n+1,t=4*n+2;
for(int i=1;i<=n;i++)scanf("%s",tmp[i]+1);
int ans,l=0,r=n;
while(l<=r)
{
int mid=l+r>>1;
build(mid);
if(dinic()==mid*n)
l=mid+1,ans=mid;
else r=mid-1;
}
printf("%d\n",ans);
return 0;
}
留言