自动搬运

查看原文

来自洛谷，原作者为

	yanchengzhi 我已竭尽全力（2023.4.2）

搬运于2025-08-24 22:30:00，当前版本为作者最后更新于2023-01-28 09:57:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

THUSCH 2017 换桌（费用流，线段树优化建图）

二分图带权匹配，可以用费用流解决。

首先有个很明显的连边方式，每个人向能去的座位连边，边数是 $\mathcal{O}(n^2m^2)$ 的，很明显不行。

考虑优化一下建图方式。

可以把桌子编号的移动和位置编号的移动分开考虑。

建立 $nm$ 个中转点，一侧的边表示桌子编号的移动，一侧的边表示位置编号的移动，这样边数就可以优化到 $\mathcal{O}(nm(n+m))$。

然后发现桌子编号的移动是一段区间，因此可以使用线段树优化建图，这样边数可以优化到 $\mathcal{O}(nm(\log n+m))$。有一个细节是绝对值的处理，这可以用两次线段树优化建图解决。

考虑继续优化，发现位置编号的移动可以连成一个环的形式，这样就可以把边数优化到 $\mathcal{O}(nm\log n)$。

#include <bits/stdc++.h>
typedef long long ll;
const int inf = 1e9;
namespace MCMF {
	const int maxN = 1e5;
	const int maxM = 1e6;
	int S, T, n, tot, maxflow, mincost;
	int head[maxN], now[maxN], dis[maxN];
	bool vis[maxN];
	struct edge {
		int to, nxt;
		int f, c;
	} e[maxM];
	void add(int u, int v, int f, int c) {
		e[++tot].to = v;
		e[tot].nxt = head[u];
		e[tot].f = f;
		e[tot].c = c;
		head[u] = tot;
	}
	void add2(int u, int v, int f, int c) {
		add(u, v, f, c);
		add(v, u, 0, -c);
	}
	bool spfa() {
		for(int i = 1; i <= n; i++) {
			dis[i] = inf;
			vis[i] = 0;
		}
		std::deque<int> q;
		q.push_back(S);
		dis[S] = 0;
		vis[S] = 1;
		while(!q.empty()) {
			int u = q.front();
			q.pop_front();
			vis[u] = 0;
			for(int i = head[u]; i; i = e[i].nxt) {
				int v = e[i].to, f = e[i].f, c = e[i].c;
				if(f && dis[u] + c < dis[v]) {
					dis[v] = dis[u] + c;
					if(!vis[v]) {
						if(!q.empty() && dis[v] < dis[q.front()]) {
							q.push_front(v);
						}
						else {
							q.push_back(v);
						}
						vis[v] = 1;
					}
				}
			}
		}
		return dis[T] < inf;
	}
	int dfs(int u, int flow) {
	    if(u == T) {
	    	return flow;
		}
	    int res = 0;
	    vis[u] = 1;
	    for(int &i = now[u]; i; i = e[i].nxt) {
	        int v = e[i].to, c = e[i].c, f = e[i].f;
			if(dis[v] == dis[u] + c && f && !vis[v]) {
				int t = dfs(v, std::min(flow, f));
				if(t) {
					flow -= t;
					res += t;
					mincost += t * c;
					e[i].f -= t;
					e[i ^ 1].f += t;
				}
				else {
					dis[v] = -inf;
				}
				if(!flow) {
					break;
				}
			}
	    }
	    vis[u] = 0;
	    return res;
	}
	void mcmf() {
	    while(spfa()) {
	    	for(int i = 1; i <= n; i++) {
	    		vis[i] = 0;
	    		now[i] = head[i];
			}
			maxflow += dfs(S, inf);
	    }
	}
	void init(int x) {
		n = x;
		S = n - 1;
		T = n;
		tot = 1;
		for(int i = 1; i <= n; i++) {
			head[i] = 0;
		}
	}
}
using MCMF::S;
using MCMF::T;
using MCMF::add2;
using MCMF::maxflow;
using MCMF::mincost;
using namespace std;
const int maxn = 305;
int n, m, cnt, l[maxn][maxn], r[maxn][maxn];
int id(int x, int y) {
	return (x - 1) * m + y;
}
#define lc (x << 1)
#define rc (x << 1 | 1)
#define mid ((l + r) >> 1)
struct SGT {
	int num[maxn * 4], leaf[maxn];
	void build_pre(int x, int l, int r) {
		num[x] = ++cnt;
		if(l == r) {
			leaf[l] = cnt;
			return;
		}
		build_pre(lc, l, mid);
		build_pre(rc, mid + 1, r);
	}
	void build(int x, int l, int r) {
		if(l == r) {
			return;
		}
		add2(num[x], num[lc], inf, 0);
		add2(num[x], num[rc], inf, 0);
		build(lc, l, mid);
		build(rc, mid + 1, r);
	}
	void link(int x, int l, int r, int L, int R, int u, int f, int c) {
		if(L > R || l > R || r < L) {
			return;
		}
		if(l >= L && r <= R) {
			add2(u, num[x], f, c);
			return;
		}
		link(lc, l, mid, L, R, u, f, c);
		link(rc, mid + 1, r, L, R, u, f, c);
	}
} A[11], B[11];
#undef lc
#undef rc
#undef mid
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> l[i][j];
			l[i][j]++;
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> r[i][j];
			r[i][j]++;
		}
	}
	/*
	O(nm(m + log n))
	cnt = n * m * 3;
	for(int i = 1; i <= m; i++) {
		A[i].build_pre(1, 1, n);
		B[i].build_pre(1, 1, n);
	}
	MCMF::init(cnt + 2);
	for(int i = 1; i <= m; i++) {
		A[i].build(1, 1, n);
		B[i].build(1, 1, n);
	}
	for(int i = 1; i <= n * m; i++) {
		add2(S, i, 1, 0);
		add2(i, i + n * m, 1, 0);
		add2(i + n * m * 2, T, 1, 0);
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			for(int k = 1; k <= m; k++) {
				add2(A[j].leaf[i], id(i, k) + n * m * 2, inf, min(abs(j - k), m - abs(j - k)) + i * 2);
				add2(B[j].leaf[i], id(i, k) + n * m * 2, inf, min(abs(j - k), m - abs(j - k)) - i * 2);
			}
			if(l[i][j] >= i) {
				A[j].link(1, 1, n, l[i][j], r[i][j], id(i, j) + n * m, 1, -i * 2);
			}
			else if(r[i][j] <= i) {
				B[j].link(1, 1, n, l[i][j], r[i][j], id(i, j) + n * m, 1, i * 2);
			}
			else {
				A[j].link(1, 1, n, i, r[i][j], id(i, j) + n * m, 1, -i * 2);
				B[j].link(1, 1, n, l[i][j], i - 1, id(i, j) + n * m, 1, i * 2);
			}
		}
	}
	*/
	// O(nm log n)
	cnt = n * m * 2;
	for(int i = 1; i <= m; i++) {
		A[i].build_pre(1, 1, n);
		B[i].build_pre(1, 1, n);
	}
	MCMF::init(cnt + 2);
	for(int i = 1; i <= m; i++) {
		A[i].build(1, 1, n);
		B[i].build(1, 1, n);
	}
	for(int i = 1; i <= n * m; i++) {
		add2(S, i, 1, 0);
		add2(i + n * m, T, 1, 0);
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			int L = j - 1 > 0 ? j - 1 : m, R = j + 1 <= m ? j + 1 : 1;
			add2(A[j].leaf[i], A[L].leaf[i], inf, 1);
			add2(A[j].leaf[i], A[R].leaf[i], inf, 1);
			add2(B[j].leaf[i], B[L].leaf[i], inf, 1);
			add2(B[j].leaf[i], B[R].leaf[i], inf, 1);
			add2(A[j].leaf[i], id(i, j) + n * m, inf, i * 2);
			add2(B[j].leaf[i], id(i, j) + n * m, inf, -i * 2);
			if(l[i][j] >= i) {
				A[j].link(1, 1, n, l[i][j], r[i][j], id(i, j), 1, -i * 2);
			}
			else if(r[i][j] <= i) {
				B[j].link(1, 1, n, l[i][j], r[i][j], id(i, j), 1, i * 2);
			}
			else {
				A[j].link(1, 1, n, i, r[i][j], id(i, j), 1, -i * 2);
				B[j].link(1, 1, n, l[i][j], i - 1, id(i, j), 1, i * 2);
			}
		}
	}
	MCMF::mcmf();
	if(maxflow < n * m) {
		cout << "no solution\n";
	}
	else {
		cout << mincost << '\n';
	}
	return 0;
}