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");
}