[CQOI2009]dance跳舞

n个男孩n个女孩, 每个男孩和每个女孩之间相互喜欢或不喜欢 (无 "单向喜欢" ). 每个男孩最多和每个女孩跳一次舞, 且只愿意和不超过k个不喜欢的女孩跳舞, 女孩亦然. 每支曲子开始时, 男女恰配成n对. 问舞会最多能有几首舞曲. (n≤50, k≤30) 男孩女孩跳舞可看成匹配, 用网络流建模, "每对最多跳一次", "只愿意和不超过k个不喜欢的异性跳舞" 可以用流量限制来描述. 具体而言, 每个男孩, 每个女孩拆成两个点, 男1向男2, 女2向女1连一条容量为k的边; 如果男a和女b相互喜欢, 则a1向b1连一条容量为1的边, 否则, a2向b2连一条容量为1的边. 本题求的是最大的x, 使每个男1的流出>x, 女1的流入>x. 源点向男1, 女1向汇点连容量为x的边, 二分x, 跑最大流验证即可.

果然Dinic的跑不满......

为了方便每次二分之后还原流量, 我同时记录了cap和flow. 在Po姐的代码中看到一种更喵的方法: 把每条边的反向边的残量清零, 加到正向边上.

以下代码不必要地把每个人拆成了3个点.

#define pb push_back

const int inf = 1e8;

namespace MF {
	const int N = 302;
	
	struct Edge {
		int v, c, f;
	};
	vector<Edge> E;
	vector<int> adj[N];

	inline void add(int u, int v, int c)
	{
		adj[u].pb(E.size());
		E.pb((Edge){v, c, 0});
		adj[v].pb(E.size());
		E.pb((Edge){u, c, c});
	}

	int lv[N], cur[N], s, t, n;

	bool bfs()
	{
		queue<int> Q;
		Q.push(s);
		fill_n(lv, n, -1);
		lv[s] = 0;

		while (!Q.empty()) {
			int u = Q.front();
			Q.pop();
			rep (i, 0, adj[u].size()) {
				Edge& e = E[adj[u][i]];
				if (e.c > e.f && lv[e.v] == -1) {
					lv[e.v] = lv[u] + 1;
					Q.push(e.v);
				}
			}
		}

		return lv[t] != -1;
	}

	int dfs(int u, int f)
	{
		if (u == t) return f;
		int res = f;
		for (int& i = cur[u]; i < (int)adj[u].size(); ++i) {
			Edge& e = E[adj[u][i]];
			if (e.c > e.f && lv[e.v] == lv[u] + 1) {
				int d = dfs(e.v, min(res, e.c - e.f));
				res -= d;
				e.f += d;
				E[adj[u][i]^1].f -= d;
				if (!res) break;
			}
		}
		return f - res;
	}

	int maximum_flow()
	{
		int f = 0;
		while (bfs()) {
			fill_n(cur, n, 0);
			f += dfs(s, inf);
		}
		return f;
	}

	inline void clean()
	{
		rep (i, 0, E.size())
			E[i].f = i & 1 ? E[i].c : 0;
	}

	void set(int m)
	{
		rep (i, 0, adj[s].size()) {
			int j = adj[s][i];
			E[j].c = E[j^1].c = E[j^1].f = m;
		}
		rep (i, 0, adj[t].size()) {
			int j = adj[t][i];
			E[j].c = E[j^1].c = E[j].f = m;
		}
	}

	inline void init(int _s, int _t, int _n)
	{
		s = _s;
		t = _t;
		n = _n;
	}
}

using MF::add;

#define S 0
#define T (6*n+1)
#define BOY(i, j) ((i)*3+(j)+1)
#define GIRL(i, j) (3*n+BOY(i, j))

const int N = 50;
char s[N+1];

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	rep (i, 0, n) {
		int b = BOY(i, 0), g = GIRL(i, 0);
		add(S, b, 0);
		add(b, b+1, inf);
		add(b, b+2, k);
		add(g, T, 0);
		add(g+1, g, inf);
		add(g+2, g, k);
		
		scanf("%s", s);
		rep (j, 0, n) {
			if (s[j] == 'Y')
				add(b+1, GIRL(j, 1), 1);
			else
				add(b+2, GIRL(j, 2), 1);
		}
	}
	
	MF::init(S, T, 6*n + 2);
	
	int l = 0, r = n+1;
	while (r-l > 1) { // [l, r)
		int m = (l+r)/2;
		MF::clean();
		MF::set(m);
		if (MF::maximum_flow() == n*m)
			l = m;
		else
			r = m;
	}

	printf("%d\n", l);
	return 0;
}