nkoj6471 小球配对 题解

有一个无限大的平面，有 $2N$ 个位置上面有若干个球（可能重复），其中 $N$ 个位置是红球，$N$ 个位置是蓝球，红球与蓝球的总数相同。

给出 $2N$ 个位置和上面的球数，现要将红球与蓝球完美匹配，匹配的权值是每一对匹配两个球的位置坐标的曼哈顿距离之和。 求最大权值。

$1\le N\le 1000$。

---

直接跑最大权二分图匹配这个1e6的边数会T飞，考虑优化建图。

一个很经典的处理绝对值的trick：$\lvert x\rvert = \max(-x,x),-\lvert x\rvert = \min(-x,x)$。

这个trick的用处在于，很多算法（常见于图论）是自带取最大/小值的功能的，比如之前做的最大分值那题就用了最小割功能，运用 $-\lvert x\rvert = \min(-x,x)$ 强拆绝对值。

这个题也不例外：

$$\lvert a-b\rvert+\lvert c-d\rvert=\max( \\a-b+c-d \\a-b-c+d \\b-a+c-d \\b-a-c+d)$$

于是对于四种情况都建一个虚点，所有红球向这四个虚点连边，四个虚点又向所有蓝球连边，通过这四个中转站把边数降到了 $O(n)$ 级别。然后跑最大权二分图匹配的时候会自动取 $\max$。

#include <cstdio>
#include <queue>
#include <cstring>
#define int long long

const int INF = 1e18;
inline int abs(int k) {return k >= 0 ? k : -k;}
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, cap, cost, nxt;
} e[4000005];
int head[10005], cur[10005], dis[10005], Maxflow, Maxcost;
int rx[1005], ry[1005], rc[1005], bx[1005], by[1005], bc[1005];
int tot = 1, s, t;
bool vis[10005], mark[10005];
std::queue<int> Q;
inline void AddEdge(int u, int v, int cap, int cost) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].cap = cap, e[tot].cost = cost;
	e[++ tot].to = u, e[tot].nxt = head[v], head[v] = tot;
	e[tot].cap = 0, e[tot].cost = -cost;
}
bool SPFA() {
	memcpy(cur, head, sizeof cur);
	memset(vis, 0, sizeof vis);
	memset(dis, ~0x3f, sizeof dis);
	memset(mark, 0, sizeof mark);
	Q.push(s);
	dis[s] = 0;
	while (Q.size()) {
		int u(Q.front());
		Q.pop();
		mark[u] = false;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (e[i].cap && dis[u] + e[i].cost > dis[v]) {
				dis[v] = dis[u] + e[i].cost;
				if (!mark[v]) Q.push(v), mark[v] = true;
			}
		}
	}
	return dis[t] > -INF;
}

int dfs(int u, int flow) {
	if (u == t) return flow;
	vis[u] = true;
	int used = 0, tmp;
	for (int i = cur[u]; i && used <= flow; i = e[i].nxt) {
		cur[u] = i;
		if (e[i].cap && dis[u] + e[i].cost == dis[e[i].to]) {
			int v = e[i].to;
			if (!vis[v] && (tmp = dfs(v, min(flow - used, e[i].cap))))
				used += tmp, e[i].cap -= tmp, e[i ^ 1].cap += tmp;
		}
	}
	return used;
}

void Dinic() {
	int flow;
	while (SPFA()) Maxflow += (flow = dfs(s, INF)), Maxcost += flow * dis[t];
}

signed main() {
	int n;
	scanf("%lld", &n);
	s = 0, t = 2 * n + 5;
    int a = 2 * n + 1, b = 2 * n + 2, c = 2 * n + 3, d = 2 * n + 4;
	for (int i = 1; i <= n; ++ i) scanf("%lld%lld%lld", rx + i, ry + i, rc + i);
	for (int i = 1; i <= n; ++ i) scanf("%lld%lld%lld", bx + i, by + i, bc + i);
	for (int i = 1; i <= n; ++ i) {
        AddEdge(s, i, rc[i], 0);
        AddEdge(i, a, INF, -rx[i] - ry[i]);
        AddEdge(i, b, INF, -rx[i] + ry[i]);
        AddEdge(i, c, INF, rx[i] - ry[i]);
        AddEdge(i, d, INF, rx[i] + ry[i]);
    }
	for (int i = 1; i <= n; ++ i) {
        AddEdge(i + n, t, bc[i], 0);
        AddEdge(a, i + n, INF, bx[i] + by[i]);
        AddEdge(b, i + n, INF, bx[i] - by[i]);
        AddEdge(c, i + n, INF, by[i] - bx[i]);
        AddEdge(d, i + n, INF, -bx[i] - by[i]);
    }
	Dinic();
	printf("%lld", Maxcost);
}