[AGC034D] Manhattan Max Matching

Problem Statement

Snuke is playing with red and blue balls, placing them on a two-dimensional plane.

First, he performed $N$ operations to place red balls. In the $i$-th of these operations, he placed $RC_i$ red balls at coordinates $(RX_i,RY_i)$.
Then, he performed another $N$ operations to place blue balls. In the $i$-th of these operations, he placed $BC_i$ blue balls at coordinates $(BX_i,BY_i)$.
The total number of red balls placed and the total number of blue balls placed are equal, that is, $\sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i$. Let this value be $S$.

Snuke will now form $S$ pairs of red and blue balls so that every ball belongs to exactly one pair.
Let us define the score of a pair of a red ball at coordinates $(rx, ry)$ and a blue ball at coordinates $(bx, by)$ as $|rx-bx| + |ry-by|$.

Snuke wants to maximize the sum of the scores of the pairs.
Help him by finding the maximum possible sum of the scores of the pairs.

Constraints

$1 \leq N \leq 1000$
$0 \leq RX_i,RY_i,BX_i,BY_i \leq 10^9$
$1 \leq RC_i,BC_i \leq 10$
$\sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i$
All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$
$RX_1$ $RY_1$ $RC_1$
$RX_2$ $RY_2$ $RC_2$
$\vdots$
$RX_N$ $RY_N$ $RC_N$
$BX_1$ $BY_1$ $BC_1$
$BX_2$ $BY_2$ $BC_2$
$\vdots$
$BX_N$ $BY_N$ $BC_N$

Output

Print the maximum possible sum of the scores of the pairs.

Sample Input 1

Sample Output 1

If we pair the red ball at coordinates $(0,0)$ and the blue ball at coordinates $(2,2)$, the score of this pair is $|0-2| + |0-2|=4$.
Then, if we pair the red ball at coordinates $(3,2)$ and the blue ball at coordinates $(5,0)$, the score of this pair is $|3-5| + |2-0|=4$.
Making these two pairs results in the total score of $8$, which is the maximum result.

Sample Input 2

Sample Output 2

Snuke may have performed multiple operations at the same coordinates.

Sample Input 3

10
582463373 690528069 8
621230322 318051944 4
356524296 974059503 6
372751381 111542460 9
392867214 581476334 6
606955458 513028121 5
882201596 791660614 9
250465517 91918758 3
618624774 406956634 6
426294747 736401096 5
974896051 888765942 5
726682138 336960821 3
715144179 82444709 6
599055841 501257806 6
390484433 962747856 4
912334580 219343832 8
570458984 648862300 6
638017635 572157978 10
435958984 585073520 7
445612658 234265014 6

Sample Output 3

45152033546

Manhattan Max Matching

曼哈顿距离其实挺难处理的，考虑将绝对值拆掉，转化为切比雪夫距离。

\[D=|x_1-x_2|+|y_1-y_2|=\max(|(x_1-y_1)-(x_2-y_2)|,|(x_1+y_1)-(x_2+y_2)|))
\]

这样看起来要跑最大费用最大流，但其实我们更习惯最小费用最大流，加上题目求的也是最小值，所以考虑取负。

\[D=-min((x_1-y_1)-(x_2-y_2),(x_1+y_1)-(x_2+y_2),(x_2+y_2)-(x_1+y_1),(x_2-y_2)-(x_1-y_1))
\]

那么此时我们要求一种匹配，让后面四个式子的 min 之和最小。既然是匹配了，考虑网络流。

先是套路，从源点向每个左节点连边，流量 $RC_i$，每个右节点向汇点连边,流量$BC_i$。

然后考虑如何求出后面四个东西最小值。建立四个虚拟节点 $s_1,s_2,s_3,s_4$，然后每个左节点 $i$ 向 $s_1$ 连一条费用 $RX_i-RY_i$ 的边，向 $s_2$ 连一条费用 $RY_i-RX_i$ 的边，其它同理。然后从 $s_1$ 向右节点连一条费用为 $BY_i-BX_i$ 的边，向 $s_2$ 连一条费用为 $BX_i-BY_i$ 的边,其它也同理。这一段所说的所有边流量正无穷。

那么此时会发现从点 $i$ 到 $j$ 的费用最短路刚好是 $|RX_i-BX_i|+|RY_i-BY_i|$。但它有那么多边，怎么让他只走最短路呢？发现跑最小费用最大流时，他自然会走最短路。所以不用考虑这件事。

但是连得费用有负数，这是一件很不好的事，这说明可能出现负环。所以考虑给他们共同加上一个一样的数。但这是否会影响最终答案呢？其实是不会的，因为发现计算中如果给他们加上 $INF$，那么 $INF$ 一共会被计算 $2*S$ 次。所以最后减去是可以的。

记得取负啊。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=4005,T=4000,S1=3999,S2=3998,S3=3997,S4=3996;
const LL INFLL=1e18,INF=2e9+5;
int n,hd[N],e_num(1),vhd[N],q[N*N],l,r,v[N],s;
LL d[N],ans;
struct edge{
	int v,nxt,f;
	LL w;
}e[N<<3];
int bfs()
{
	memcpy(hd,vhd,sizeof(hd));
	memset(v,0,sizeof(v));
	memset(d,0x7f,sizeof(d));
	d[q[l=r=1]=0]=1,v[0]=1;
//	printf("%d\n",hd[0]);
	while(l<=r)
	{
//		printf("%d\n",q[l]);
		for(int i=hd[q[l]];i;i=e[i].nxt)
		{
			if(d[e[i].v]>d[q[l]]+e[i].w&&e[i].f)
			{
				d[e[i].v]=d[q[l]]+e[i].w;
				if(!v[e[i].v])
					v[q[++r]=e[i].v]=1;
			}
		}
		v[q[l++]]=0;
	}
//	printf("%lld\n",d[T]);
	return d[T]<=INFLL;
}
int dfs(int x,int s)
{
//	printf("%d %d\n",x,s);
	if(x==T)
		return s;
	v[x]=1;
	LL g;
	for(int&i=hd[x];i;i=e[i].nxt)
	{
		if(e[i].f&&!v[e[i].v]&&d[e[i].v]==d[x]+e[i].w&&(g=dfs(e[i].v,min(s,e[i].f))))
		{
			e[i].f-=g;
			e[i^1].f+=g;
			ans+=e[i].w*g;
			return g;
		}
	}
	return 0;
}
void add_edge(int u,int v,int f,LL w)
{
	e[++e_num]=(edge){v,hd[u],f,w};
	hd[u]=e_num;
	e[++e_num]=(edge){u,hd[v],0,-w};
	hd[v]=e_num;
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x,y,c;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&c),add_edge(0,i,c,0),s+=c;
		add_edge(i,S1,INF,INF+x+y);
		add_edge(i,S2,INF,INF+x-y);
		add_edge(i,S3,INF,INF-x-y);
		add_edge(i,S4,INF,INF+y-x);
	}
	for(int i=1,x,y,c;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&c),add_edge(i+n,T,c,0);
		add_edge(S1,i+n,INF,INF-x-y);
		add_edge(S2,i+n,INF,INF+y-x);
		add_edge(S3,i+n,INF,INF+x+y);
		add_edge(S4,i+n,INF,INF+x-y);
	}
	memcpy(vhd,hd,sizeof(hd));
	while(bfs())
		while(dfs(0,INF));
	printf("%lld",2LL*INF*s-ans);
	return 0;
}

原文链接: https://www.cnblogs.com/mekoszc/p/17049355.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/311918

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！