【UOJ #171】【WC 2016】挑战NPC

http://uoj.ac/problem/171

带花树开花时的u和v一定要记清楚顺序，想好了再写，数据范围也要算好！

对每个筐子拆成3个点，连成一个三元环，对每个(u,v)，让u和v的3个点都连边，这样跑一般图最大匹配（先增广每个球），可以发现所有的球都能放到一个筐子里，而且半空的筐子代表的三元环一定有一条边有匹配。

匹配总数=n+半空的筐子数，最大化匹配总数也相当于最大化半空的筐子数。

还可以发现三元环没必要连三条边，任选两个点连一条边也是一样的。

时间复杂度\(O(n^3)\)。

abclzr：“好神的建图啊，我一辈子也想不出来。”

reflash：“没关系，下辈子继续想。”

abclzr：“……”

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = 603;

const int M = 100003;

struct node {int nxt, to;} E[M << 1];

int cnt, point[N], n, m, e, s[N], qu[N];

void ins(int u, int v) {E[++cnt] = (node) {point[u], v}; point[u] = cnt;}

int tt[N], id[N], tot, fa[N], pre[N], Next[N];

int find(int x) {return fa[x] == x ? x : (fa[x] = find(fa[x]));}

int p, q, tim = 0, vis[N];

int findlca(int u, int v) {

	++tim;

	while (true) {

		if (u) {

			if (vis[u] == tim)

				return u;

			vis[u] = tim;

			u = find(pre[Next[u]]);

		}

		swap(u, v);

	}

}

void blossom(int u, int v, int lca) {

	while (find(u) != lca) {

		pre[u] = v;

		v = Next[u];

		if (s[v] == 1) {s[v] = 0; if (++q == N) q = 0; qu[q] = v;}

		if (fa[u] == u) fa[u] = lca;

		if (fa[v] == v) fa[v] = lca;

		u = pre[v];

	}

}

int match(int x) {

	memset(s, -1, sizeof(int) * (tot + 1));

	for (int i = 1; i <= tot; ++i) fa[i] = i;

	p = 0; q = 1; s[qu[1] = x] = 0; pre[x] = 0;

	int u, v;

	while (p != q) {

		if (++p == N) p = 0; u = qu[p];

		for (int i = point[u]; i; i = E[i].nxt) {

			v = E[i].to;

			if (s[v] == -1) {

				s[v] = 1; pre[v] = u;

				if (!Next[v]) {

					int last;

					while (u) {

						last = Next[u];

						Next[u] = v; Next[v] = u;

						u = pre[v = last];

					}

					return 1;

				}

				s[Next[v]] = 0; if (++q == N) q = 0; qu[q] = Next[v];

			} else if (s[v] == 0 && find(u) != find(v)) {

				int lca = findlca(fa[u], fa[v]);

				blossom(u, v, lca);

				blossom(v, u, lca);

			}

		}

	}

	return 0;

}

int main() {

	int T; scanf("%d", &T);

	while (T--) {

		scanf("%d%d%d", &n, &m, &e);

		tt[0] = n - 2;

		for (int i = 1; i <= m; ++i) {

			tt[i] = tt[i - 1] + 3;

			id[tt[i]] = id[tt[i] + 1] = id[tt[i] + 2] = i;

		}

		int u, v; tot = tt[m] + 2;

		cnt = 0;

		memset(point, 0, sizeof(int) * (tot + 1));

		memset(Next, 0, sizeof(int) * (tot + 1));

		for (int i = 1; i <= e; ++i) {

			scanf("%d%d", &u, &v);

			ins(u, tt[v]); ins(tt[v], u);

			ins(u, tt[v] + 1); ins(tt[v] + 1, u);

			ins(u, tt[v] + 2); ins(tt[v] + 2, u);

		}

		for (int i = 1; i <= m; ++i) ins(tt[i], tt[i] + 1), ins(tt[i] + 1, tt[i]);

		int ans = 0;

		for (int i = 1; i <= tot; ++i)

			if (!Next[i])

				ans += match(i);

		printf("%d\n", ans - n);

		for (int i = 1; i <= n; ++i)

			printf("%d ", id[Next[i]]);

		puts("");

	}

	return 0;

}

巴特西

【UOJ #171】【WC 2016】挑战NPC

最新文章

热门文章