CWOI S C0223 C 金條爭奪 | EarthMessenger 博客

題面使用 openssl enc -aes256 -a -pbkdf2 加密。

U2FsdGVkX1/R+S8iPQV0IX213X4XhnMFL64nWtdaygIV5tSJ9Nra94D363mkeWl9
0IFudn+Anw+SCvrsOzyC2phjAT4Y51iI0Vx9RHAOMvy6CDzb/U6JY927QfdagEv1
p8PdiQF2NCp6Rc2zs+GSmMkWxGM3DDNiFPjHEf+yMkGWfN/D5VS+myWWQJmfGXJS
3tnY7tFbNZvN010uQRO1MHOUhoGqTjxvt+wmE2Jm4i1kjXBtP/OUHs9sqIpwq8Ra
sDa3UqAnvMvD6hRRcvv2jyb8c5mQBuEh3ZAR6choEXzvYDGKHWKTNHPk/0R2dm0r
0qXgM2mgH2u/1k8J7ACKTNMVWfewwTFJ3HAP1PptS2LzYLZvSGDDF/rGsUimADh0
OOIoLjQlnUrsEY8r8RLCcti1RuvEw96dak6m02/ZUScq9+NJi0EMPJDy75j0sXUo
IAn/aMlD7hC48/dCA81q0IEx5QD8FoVVJCbUhsi9KWxNuqGl9/48R5+FeVIEgduZ
ODjpynOyxm58Vpv9VK4y8xFJNSEqqnfzEYBa3MndoHc9v+jme6Ax4S8CpMCeOT5r
pl7R9rjyEydR74vW6o5drEXHRBoeJKVJzgwVrXqLrcGlzn1mvBY9sqDhXQV3oXRC
yQ9CCN97pE+gPFffz710pDHPrM2MWBw+SRW9w6q9/SEzSZKX81216I7LL3m5++cr
XfIf74hSvDyImP8K+9WzHa2czRoPKSiyJ4cyBN7Ql/zBq2h/gCPcSn4oSyu6mcYg
rUAhdDMEdX8dZteIB7uNlnJ0xsUEGwYk+X9MbxJ1fkQfUXDqVmmLektxO/tBhyCL

首先可以分析出的是，最多隻會出現一次爭奪，如果某個人爭奪金條後再次被爭奪，那麼他會由得到金條變為遺憾離場，不如沒有決策。

這個問題可以轉化成二分圖博弈問題。在二分圖上移動棋子就相當於爭奪一次金條。如果從 $X$ 開始，先手必勝，則會產生一次爭奪，反之不會。

如何判斷先手必勝？先手必勝的充要條件是起始點在所有的最大匹配中都為匹配點。充分性：當最大匹配一定包含 $X$ 時，先手每次選擇任意一條匹配邊，而後手一定選不到非匹配點。如果後手選到非匹配點，則說明路徑上有兩個相鄰的非匹配邊，可以整體交錯一下，這樣便得到了一個不包含 $X$ 的最大匹配，矛盾。必要性：當存在一個最大匹配不一定包含 $X$ 時，考慮一種不包含 $X$ 的最大匹配 $M$ ，第一步時先手一定會選到匹配點，否則存在更大匹配。之後後手只需要不斷選擇匹配邊即可，先手一定會選到匹配點，否則把路徑整體交錯一下又會得到更大的匹配。

所以問題就轉變成了判斷 $X$ 是否一定包含在最大匹配中，與判斷某條邊是否可能包含在最大匹配中。

判斷 $X$ 是否包含在最大匹配中，可以先在沒有 $X$ 的圖上跑一遍最大匹配，再把 $X$ 加到圖中，看最大匹配是否增加。

判斷某條邊是否可能在最大匹配中，方法是先用網路流求出一組二分圖最大匹配，再在殘量網路上縮點。

如果邊出現在求出的哪組最大匹配中，顯然可能。
如果沒有出現，設邊的兩個端點為 $u$ $u$ 和 $v$ $v$ 。
- 如果 $u$ $u$ 和 $v$ $v$ 各自都有匹配的話，設 $u$ $u$ 匹配 $x$ $x$ ， $v$ $v$ 匹配 $y$ $y$ 。
  - 如果存在 $x$ 到 $y$ 的邊時，可以把這個環交錯一下，得到一條包含 $u-v$ 邊的最大匹配。此時 $u$ , $v$ , $x$ , $y$ 都在一個強連通分量中。
  - 如果不存在，則 $u-v$ 不可能在某種最大匹配中，也不在一個強連通分量中。
- 如果 $u$ 和 $v$ 其中之一有匹配的話，欽定有匹配的點為 $u$ ，設 $u$ 匹配 $w$ ，交錯一下便可以得到一種包含 $u-v$ 的最大匹配。此時 $u$ 連向 $v$ ， $v$ 連向匯點 $T$ ， $T$ 又連向 $w$ ， $w$ 又連向 $u$ ，四個點在一個強連通分量中。

極長的程式碼：

#include <algorithm>
#include <cstdio>
#include <limits>
#include <queue>
#include <stack>
#include <utility>
#include <vector>

struct tarjan_algorithm
{
	int n;
	std::vector<std::vector<int>> adj;

	std::vector<int> dfn, low;
	int dfn_cnt;
	std::stack<int> stack;
	std::vector<bool> in_stack;
	std::vector<int> scc;
	int scc_cnt;

	tarjan_algorithm(int n) : 
		n(n), adj(n), dfn(n, -1), low(n), dfn_cnt(0), in_stack(n), scc(n), scc_cnt(0) {}

	void add_edge(int u, int v)
	{	
		adj[u].emplace_back(v);
	}

	void dfs(int u) {
		low[u] = dfn[u] = dfn_cnt++;
		stack.emplace(u);
		in_stack[u] = true;

		for (auto v : adj[u]) {
			if (dfn[v] == -1) {
				dfs(v);
				low[u] = std::min(low[u], low[v]);
			} else if (in_stack[v]) {
				low[u] = std::min(low[u], dfn[v]);
			}
		}
		if (dfn[u] == low[u]) {
			int tmp;
			do {
				tmp = stack.top();
				stack.pop();
				in_stack[tmp] = false;
				scc[tmp] = scc_cnt;
			} while (tmp != u);
			scc_cnt++;
		}
	}

	bool same_scc(int i, int j)
	{
		return scc[i] == scc[j];
	}
};

struct dinic_algorithm
{
	int n;
	int s, t;
	
	struct flow_edge
	{
		int u, v;
		int cap, flow;
		flow_edge(int u, int v, int cap) : u(u), v(v), cap(cap), flow(0) {}
	};
	std::vector<flow_edge> edges;
	std::vector<std::vector<int>> adj;

	std::vector<int> level, ptr;

	dinic_algorithm(int n, int s, int t) : n(n), s(s), t(t), adj(n), level(n), ptr(n) {}

	void add_edge(int u, int v, int cap)
	{
		adj[u].emplace_back((int)edges.size());
		edges.emplace_back(u, v, cap);
		adj[v].emplace_back((int)edges.size());
		edges.emplace_back(v, u, 0);
	}

	bool bfs()
	{
		std::fill(level.begin(), level.end(), -1);
		level[s] = 0;
		std::queue<int> q;
		q.emplace(s);
		while (!q.empty()) {
			int u = q.front();
			q.pop();
			for (auto id : adj[u]) {
				if (edges[id].cap - edges[id].flow < 1) continue;
				if (level[edges[id].v] != -1) continue;
				level[edges[id].v] = level[u] + 1;
				q.emplace(edges[id].v);
			}
		}
		return level[t] != -1;
	}

	int dfs()
	{
		return dfs(s, std::numeric_limits<int>::max());
	}

	int dfs(int u, int flow_limit)
	{
		if (u == t || flow_limit == 0) return flow_limit;
		int res = 0;
		for (int &cid = ptr[u]; cid < (int)adj[u].size(); cid++) {
			int id = adj[u][cid];
			int v = edges[id].v;
			if (level[v] != level[u] + 1 || edges[id].cap - edges[id].flow < 1)
				continue;
			int d = dfs(v, std::min(flow_limit, edges[id].cap - edges[id].flow));
			if (d == 0) continue;
			res += d;
			edges[id].flow += d;
			edges[id ^ 1].flow -= d;
			if (res == flow_limit) return res;
		}
		return res;
	}

	int flow()
	{
		int res = 0;
		while (true) {
			if (!bfs()) break;
			std::fill(ptr.begin(), ptr.end(), 0);
			while (int f = dfs()) {
				res += f;
			}
		}
		return res;
	}

	tarjan_algorithm export_to_tarjan()
	{
		tarjan_algorithm res(n);
		for (auto e : edges) {
			if (e.cap - e.flow < 1) continue;
			res.add_edge(e.u, e.v);
		}
		return res;
	}
};

int main()
{
	int n, m;
	int P, X, k;
	scanf("%d%d%d%d%d", &n, &m, &P, &X, &k);
	X--;
	if (P == 2) std::swap(n, m);

	std::vector<std::vector<bool>> love(n, std::vector<bool>(m));

	for (int i = 0; i < k; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--;
		v--;
		if (P == 2) std::swap(u, v);
		love[u][v] = true;
	}

	std::vector<std::vector<int>> ans(2);
	ans[0].assign(n, 1);
	ans[1].assign(m, 1);
	ans[0][X] = 2;

	dinic_algorithm da(n + m + 2, n + m, n + m + 1);

	for (int i = 0; i < n; i++) {
		if (i == X) continue;
		for (int j = 0; j < m; j++) {
			if (love[i][j]) continue;
			da.add_edge(i, j + n, 1);
		}
	}

	for (int i = 0; i < n; i++) da.add_edge(n + m, i, 1);
	for (int i = 0; i < m; i++) da.add_edge(i + n, n + m + 1, 1);

	int old_flow = da.flow();

	for (int j = 0; j < m; j++) {
		if (love[X][j]) continue;
		da.add_edge(X, j + n, 1);
	}

	int new_flow = da.flow() + old_flow;

	// printf("old: %d\n", old_flow);
	// printf("new: %d\n", new_flow);

	if (old_flow == new_flow) {
		if (P == 2) std::swap(ans[0], ans[1]);
		for (int i = 0; i < (int)ans[0].size(); i++) {
			printf("%d ", ans[0][i]);
		}
		printf("\n");
		for (int i = 0; i < (int)ans[1].size(); i++) {
			printf("%d ", ans[1][i]);
		}
		printf("\n");
		return 0;
	}

	auto tarjan = da.export_to_tarjan();
	tarjan.dfs(0);

	// for (int i = 0; i < n + m + 2; i++) {
	// 	printf("%d belong : %d\n", i, tarjan.scc[i]);
	// }

	int winner = -1;
	for (auto e : da.edges) {
		// printf("%d -> %d ( %d / %d )\n", e.u, e.v, e.flow, e.cap);
		if (e.u != X || e.v >= n + m) continue;
		if (e.cap - e.flow < 1 || tarjan.same_scc(e.u, e.v)) {
			if (winner == -1 || winner > e.v - n) {
				winner = e.v - n;
			}
		}
	}

		ans[1][winner] = 2;
		ans[0][X] = 0;

	if (P == 2) std::swap(ans[0], ans[1]);
	for (int i = 0; i < (int)ans[0].size(); i++) {
		printf("%d ", ans[0][i]);
	}
	printf("\n");
	for (int i = 0; i < (int)ans[1].size(); i++) {
		printf("%d ", ans[1][i]);
	}
	printf("\n");
}