CF847J Students Initiation

题意

有 \(n\) 个人，\(m\) 对关系，要求每对关系中，有且仅有一个人给另外一个人送礼物，并且使送出礼物最多的人送的礼物尽可能少。并输出送礼物的方案。

Sol

二分答案，对于每个人向每个限制连 \(1\) 容量，每个限制向汇点连 \(1\) 容量。

Code

array <pii, N> isl;

bool check(int x, int n, int m) {
	G::cnt = 1, G::fir.fill(0);
	pii st(m + n + 1, m + n + 2);
	for (int i = 1; i <= m; i++) {
		G::_add(isl[i].fi, n + i, 1);
		G::_add(isl[i].se, n + i, 1);
		G::_add(n + i, st.se, 1);
	}
	for (int i = 1; i <= n; i++)
		G::_add(st.fi, i, x);
	return Mfl::dinic(st) == m;
}

array <int, N> _ans;

signed main() {
	int n = read(), m = read();
	for (int i = 1; i <= m; i++)
		isl[i] = make_pair(read(), read());
	if (!m) return puts("0"), 0;
	int l = 1, r = n;
	int ans = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		/* write(l), putchar(32); */
		/* write(r), putchar(32); */
		/* write(mid), puts(""); */
		if (check(mid, n, m)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	check(ans, n, m);
	for (int i = 1; i <= n; i++)
		for (int j = G::fir[i]; j; j = G::nex[j])
			if (G::to[j] > n && G::to[j] != n + m + 1 && !G::cap[j])
				_ans[G::to[j] - n] = i;
	write(ans), puts("");
	for (int i = 1; i <= m; i++) {
		int x, y; tie(x, y) = isl[i];
		/* write(_ans[i]), puts(""); */
		if (x != _ans[i]) swap(x, y);
		write(x), putchar(32);
		write(y), puts("");
	}
	return 0;
}