u1s1，网上的题解都好简洁啊，蒟蒻表示根本看不懂（

$\texttt{Description}$

题面过于复杂，见题面

$\texttt{Solution}$

由于只计算使用超能力的次数，所以天兵放哪里无所谓。

（以下的讨论均不考虑天兵）

每次交换操作可以看成是交换一个兵的种类，即骑兵变成步兵，步兵变成骑兵。由于步兵和骑兵的数量是相同的，所以一定不会出现不合法的交换。

然后就可以想到SPFA预处理一下 $dis_{i,j}$ 表示第 $i$ 个兵最少需要用几次超能力才能到第 $j$ 个目标格子。这里把一个需要有 $r$ 个兵进入的格子拆成了 $r$ 个相同的格子，原因后面就会看到。

由于直接计算答案很麻烦，考虑二分答案 $mid$，对于每个 $dis_{i,j}$，如果它大于 $mid$ 不管，小于等于就加一条 $i$ 到 $j$ 的边。因为我们想要尽可能多的在不加入天兵的干涉时尽可能多的让这些兵到达目标位置，所以对建出来的这个图跑一遍最大匹配即可。假设可以有 $cnt$ 个兵到达互不相同的目标格（这里前面拆格子的作用就体现出来了，因为一个需要多个兵进入的格子在图上实际上是多个点）。假设跑出来的最大匹配是 $cnt$。

但是我们还没有考虑天兵。这个题有点玩文字游戏的意思，其实想一想会发现天兵的作用就是到达一个目标格然后可以与其它兵交换，即保证了这个问题有解。那么如果二分了一个 $mid$，天兵就可以送 $mid$ 次其它的兵到目标格。注意每次超能力可以交换无限次兵的位置，因为天兵与其它兵的交换和步兵与骑兵的交换是独立的（独立指两次交换不会操作一个相同的兵，如果不独立，那么肯定不是最优解，所以不用管）。最后就得出如果 $cnt+mid\ge 2\times k$ 就是可行的一个答案。

$\texttt{Code}$

#include <cstdio>
#include <queue>
#include <cstring>

inline int min(const int x, const int y) {return x < y ? x : y;}
struct Node {int x, y;};
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
std::queue<Node> Q;
std::vector<int> G[105];

int lnk[105], x[105], y[105], dis[105][205], tp[105][105], h[105][105];
int rx[105], ry[105], n, m, k, tot;
bool vis[105], mark[105][105];
bool Find(const int u) {
	for (int v : G[u]) 
		if (!vis[v] && (vis[v] = true))
			if (!lnk[v] || Find(lnk[v])) return lnk[v] = u, true;
	return false;
}

void SPFA(const int sx, const int sy, const int d) {
	memset(mark, 0, sizeof mark);
	memset(tp, 0x3f, sizeof tp);
	tp[sx][sy] = 0;
	Q.push(Node{sx, sy});
	while (Q.size()) {
		int x(Q.front().x), y(Q.front().y);
		Q.pop();
		mark[x][y] = false;
		for (int k(0); k <= 3; ++ k) {
			int x0(x + dx[k]), y0(y + dy[k]);
			if (x0 < 1 || n < x0 || y0 < 1 || m < y0) continue;
			int ans(0), tmp((tp[x][y] & 1) ^ d);
			if (h[x][y] < h[x0][y0] && tmp) ans = 1;
			if (h[x][y] > h[x0][y0] && !tmp) ans = 1;
			if (tp[x][y] + ans < tp[x0][y0]) {
				tp[x0][y0] = tp[x][y] + ans;
				if (!mark[x0][y0])
					Q.push(Node{x0, y0}), mark[x0][y0] = true;
			}
		}
	}
}

bool check(const int mid) {
	memset(lnk, 0, sizeof lnk);
	int ans(0);
	for (int i(1); i <= 2 * k; ++ i) G[i].clear();
	for (int i(1); i <= 2 * k; ++ i);
	for (int i(1); i <= 2 * k; ++ i)
		for (int j(1); j <= tot; ++ j)
			if (dis[i][j] <= mid) G[i].push_back(j);
	for (int i(1); i <= 2 * k; ++ i)
		memset(vis, 0, sizeof vis), ans += Find(i);
	return ans + mid >= 2 * k;
}

int main() {
	int t, l(0), r;
	scanf("%d%d%d%d", &n, &m, &k, &t);
	for (int i(1); i <= 2 * k + 1; ++ i) scanf("%d%d", x + i, y + i);
	for (int i(1); i <= t; ++ i) {
		int x, y, r;
		scanf("%d%d%d", &x, &y, &r);
		while (r --) rx[++ tot] = x, ry[tot] = y;
	}
	for (int i(1); i <= n; ++ i)
	for (int j(1); j <= m; ++ j) scanf("%d", &h[i][j]);
	for (int i(1); i <= 2 * k; ++ i) {
		SPFA(x[i], y[i], i > k);
		for (int j(1); j <= tot; ++ j) dis[i][j] = tp[rx[j]][ry[j]];
	}
	r = 2 * k;
	while (l < r) {
		int mid(l + r >> 1);
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d", l);
	return 0;
}

zqs`s blog

题解【P7198 [CTSC2002]玩具兵】

$\texttt{Description}$

$\texttt{Solution}$

$\texttt{Code}$