「WC2016」挑战NPC

「WC2016」挑战NPC

解题思路

这个题建图非常厉害，带花树什么的只会口胡根本写不动，所以我写了机房某大佬教我的乱搞。

考虑把一个筐 \(x\) 拆成 \(x1,x2,x3\) 三个点，且这三个点相互连边，每对球和筐的连边都让球和筐拆出的三个点连边，这样如果筐内部的点存在一个匹配，那么这个筐就是半空的，所以我们需要先将球匹配完，然后不断尝试增广来自筐的点，每一次成功增广都使得答案 \(+1\) ，一般图最大匹配跑跑就好了。

下面的代码随时可能在 \(\text{uoj}\) 上变成 \(\text{97pts}\) 。

code

/*program by mangoyang*/

#include<bits/stdc++.h>

#define inf (0x7f7f7f7f)

#define Max(a, b) ((a) > (b) ? (a) : (b))

#define Min(a, b) ((a) < (b) ? (a) : (b))

typedef long long ll;

using namespace std;

template <class T>

inline void read(T &x){

    int ch = 0, f = 0; x = 0;

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;

    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;

    if(f) x = -x;

}

const int N = 100005;

vector<int> g[N];

int a[N], b[N], vis[N], mat[N], tim, n, m, e, ans;

inline int dfs(int u){

	if(!u) return 1; vis[u] = tim;

	random_shuffle(g[u].begin(), g[u].end());

	for(int i = 0; i < (int) g[u].size(); i++){

		int v = g[u][i], x = mat[v];

		if(vis[x] == tim) continue;

		mat[u] = v, mat[v] = u, mat[x] = 0;

		if(dfs(x)) return 1;

		mat[u] = 0, mat[x] = v, mat[v] = x;

	}

	return 0;

}

inline void XJB_blossom(){

	int tot1 = 0, tot2 = 0;

	for(int i = 1; i <= n; i++) a[++tot1] = i;

	for(int i = n + 1; i <= n + 3 * m; i++) b[++tot2] = i;

	for(int T = 1; T <= 20; T++){

		random_shuffle(a + 1, a + tot1 + 1), ++tim;

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

			if(!mat[a[i]]) ans += dfs(a[i]);

	}

	for(int T = 1; T <= 20; T++){

		random_shuffle(b + 1, b + tot2 + 1), ++tim;

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

			if(!mat[b[i]]) ans += dfs(b[i]);

	}

}

inline void addedge(int x, int y){

	g[x].push_back(y), g[y].push_back(x);

}

inline void solve(){

	read(n), read(m), read(e), tim = ans = 0;

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

		addedge(n + (i - 1) * 3 + 1, n + (i - 1) * 3 + 2);

		addedge(n + (i - 1) * 3 + 1, n + (i - 1) * 3 + 3);

		addedge(n + (i - 1) * 3 + 2, n + (i - 1) * 3 + 3);

	}

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

		read(x), read(y);

		addedge(x, n + (y - 1) * 3 + 1);

		addedge(x, n + (y - 1) * 3 + 2);

		addedge(x, n + (y - 1) * 3 + 3);

	}

	XJB_blossom();

	cout << ans - n << endl;

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

		printf("%d ", (mat[i] - n - 1) / 3 + 1);

	for(int i = 1; i <= n + 3 * m; i++)

		vis[i] = mat[i] = 0, g[i].clear();

}

int main(){

	srand(time(NULL));

	int T; read(T); while(T--) solve();

	return 0;

}