• 原题链接

题目大意

给 $n$ 个男孩和 $n$ 个女孩，选出来 $n$ 对跳一次舞，且两个人只能共同跳一次舞，要求跳舞次数最大。有的男孩女孩互相喜欢（一个人可能有很多喜欢的人），且不会有单相思，一个男孩只会和他不喜欢的女孩跳 $k$ 次舞，女孩也同理。

建模

首先考虑 $k$ 的限制，通过直觉或者几次尝试我们发现可以用网络流问题中比较经典的拆点思想。

把一个人拆成两个点，一个向喜欢的人连边，一个向不喜欢的人连边，流量均为一。自己从向喜欢的人连边的点向向不喜欢的人连边的点连边，流量为 $k$。（都为有向边）

如果没有需要 $n$ 对来组成一首曲子的限制的话，我们可以直接设源点到每个男孩之间有一条流量为无限的边，女孩到汇点之间也有一条。不过由于场次的限制我们需要一些改变。

我们可以先把无限的流量改为一，然后跑多次最大流。如果流量是 $n$ 则说明可以跳舞，增加一次答案后将源点向男孩，女孩向汇点的边全部重置一遍，然后接着跑最大流。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 2e6 + 10;
const int inf = 0x3f3f3f3f;
int n, k, s, t;
int cnt = 1;
int head[N];
struct edge {
	int u, v, c, nxt;
	edge(int u = 0, int v = 0, int c = 0, int nxt = 0) : u(u), v(v), c(c), nxt(nxt) {}
} e[M * 2];
void ADD(int u, int v, int c) {
	cnt++;
	e[cnt] = edge(u, v, c, head[u]);
	head[u] = cnt;
}
void add_edge(int u, int v, int c) {
	ADD(u, v, c);
	ADD(v, u, 0);
}
int dep[N];
int now[N];
bool bfs() {
	memset(dep, 0, sizeof dep);
	memcpy(now, head, sizeof head);
	queue<int>q;
	dep[s] = 1;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].v;
			int c = e[i].c;
			if (dep[v] != 0 || !c) continue;
			dep[v] = dep[u] + 1;
			q.push(v);
		}
	}
	return dep[t] != 0;
}
int dfs(int u, int t, int flow) {
	if (u == t) return flow;
	int nowflow = 0;
	for (int i = now[u]; i; i = e[i].nxt) {
		now[u] = i;
		int v = e[i].v;
		int c = e[i].c;
		if (dep[v] != dep[u] + 1 || !c ) continue;
		int ff = dfs(v, t, min(flow, c));
		if (ff) flow -= ff, nowflow += ff, e[i].c -= ff, e[i ^ 1].c += ff;
	}
	return nowflow;
}
bool maxflow() {
	int mxflow = 0;
	int nowflow;
	while (bfs()) {
		while ((nowflow = dfs(s, t, inf))) mxflow += nowflow;
		if (mxflow >= n) return 1;
	}
	return 0;
}
int re1[N];
int re2[N];
int main() {
	cin >> n >> k;
	s = n * 4 + 1, t = n * 4 + 2;
	for (int i = 1; i <= n; i++) {
		add_edge(i, n * 2 + i, k);
		add_edge(n * 3 + i, n + i, k);
		string a;
		cin >> a;
		for (int j = 0; j < n; j++) {
			if (a[j] == 'Y') add_edge(i, j + 1 + n, 1);
			else add_edge(n * 2 + i, j + 1 + n*3, 1);
		}
	}
	int tot = 0;
	for (int i = 1; i <= n; i++) add_edge(s, i, 1), re1[i] = cnt - 1, add_edge(i + n, t, 1), re2[i] = cnt - 1;
	while (maxflow()) {
		tot++;
		for (int i = 1; i <= n; i++) {
			e[re1[i]].c += e[re1[i] ^ 1].c;
			e[re1[i] ^ 1].c = 0;
			e[re2[i]].c += e[re2[i] ^ 1].c;
			e[re2[i] ^ 1].c = 0;
		}
	}
	cout << tot;
}