自动搬运

查看原文

来自洛谷，原作者为

	xht 好想爱这个世界啊

搬运于2025-08-24 21:33:20，当前版本为作者最后更新于2019-03-12 01:19:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目地址：P2045 方格取数加强版

1. 点边转化：把每个格子 $(i,j)$ 拆成一个入点一个出点。
2. 从每个入点向对应的出点连两条有向边：一条容量为 $1$ ，费用为格子 $(i,j)$ 中的数；另一条容量为 $k-1$ ，费用为 $0$ 。
3. 从 $(i,j)$ 的出点到 $(i,j+1)$ 和 $(i+1,j)$ 的入点连有向边，容量为 $k$ ，费用为 $0$ 。
4. 以 $(1,1)$ 的入点为源点， $(n,n)$ 的出点为汇点，求最大费用最大流。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 6, M = 2e5 + 6;
const int inf = 0x3f3f3f3f, _inf = 0xcfcfcfcf;
int Head[N], Edge[M], Leng[M], Cost[M], Next[M], tot = 1;
int d[N], f[N], p[N];
bool v[N];
int n, k, s = 1, t, ans;

inline void add(int x, int y, int z, int c) {
	Edge[++tot] = y;
	Leng[tot] = z;
	Cost[tot] = c;
	Next[tot] = Head[x];
	Head[x] = tot;
	Edge[++tot] = x;
	Leng[tot] = 0;
	Cost[tot] = -c;
	Next[tot] = Head[y];
	Head[y] = tot;
}

inline int num(int i, int j, int k) {
	return (i - 1) * n + j + k * n * n;
}

inline bool spfa() {
	queue<int> q;
	memset(d, 0xcf, sizeof(d));
	memset(v, 0, sizeof(v));
	q.push(s);
	d[s] = 0;
	v[s] = 1;
	f[s] = inf;
	while (q.size()) {
		int x = q.front();
		v[x] = 0;
		q.pop();
		for (int i = Head[x]; i; i = Next[i]) {
			if (!Leng[i]) continue;
			int y = Edge[i];
			if (d[y] < d[x] + Cost[i]) {
				d[y] = d[x] + Cost[i];
				f[y] = min(f[x], Leng[i]);
				p[y] = i;
				if (!v[y]) {
					q.push(y);
					v[y] = 1;
				}
			}
		}
	}
	return d[t] != _inf;
}

void upd() {
	int x = t;
	while (x != s) {
		int i = p[x];
		Leng[i] -= f[t];
		Leng[i^1] += f[t];
		x = Edge[i^1];
	}
	ans += d[t] * f[t];
}

int main() {
	cin >> n >> k;
	t = 2 * n * n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++) {
			int c;
			scanf("%d", &c);
			add(num(i, j, 0), num(i, j, 1), 1, c);
			add(num(i, j, 0), num(i, j, 1), k - 1, 0);
			if (j < n) add(num(i, j, 1), num(i, j + 1, 0), k, 0);
			if (i < n) add(num(i, j, 1), num(i + 1, j, 0), k, 0);
		}
	while (spfa()) upd();
	cout << ans << endl;
	return 0;
}