题意
有 \(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;
}