OI - Manhattan Max Matching (AtCoder) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Manhattan Max Matching (AtCoder)

发表于 更新于 分类于 Valine：

想到了费用流，但是没有想到可以这样处理绝对值……

Part1. 题意

(中文题面是 wzy yy 的)

一个平面直角坐标系上有 $n$ 堆山楂和 $n$ 堆柠檬，第 $i$ 堆山楂有 $t_i$ 个，放在坐标 $(x_i,y_i)$，第 $i$ 堆柠檬有 $t_i’$ 个，放在坐标 $(x_i’,y_i’)$。

这 $n$ 堆柠檬的总数和 $n$ 堆山楂的总数相等，即 $\sum_{i=1}^nt_i=\sum_{i=1}^nt_i’$。

你现在要进行下述操作：
分别选择一堆柠檬和一堆山楂，从中分别拿出 一个 柠檬和山楂；获得的酸度值是这两堆东西的曼哈顿距离。（当一堆东西被拿完后，那一堆就消失了）

显然你可以在若干次操作后拿完所有山楂和柠檬。那么，你最酸可以达到多少？（酸度值的最大值）

Hint. $1\le n\le1000$，$1\le t_i,t_i’\le10$，$0\le x_i,y_i,x_i’,y_i’\le10^9$；

Part2. 考场思路

一来就看到这是个二分图……

最初想的是一个 完全匹配，但是发现这个是边权而非点权，匈牙利算法肯定跑不了（而且时间也会爆炸）。

然后就想到网络流也可以解决匹配问题，又带边权，自然想到这可以跑 最大费用流！感觉没有什么问题，接下来就开始想建图了。

感觉对绝对值这个东西非常的熟悉，但是到计算一堆绝对值的最大值的时候就有一点懵……最后只有暴力建 $n^2$ 条边，也就是每堆山楂和每堆柠檬连边。

当然会 TLE 了。

Part3. 正解

其实我在考场上没有考虑到绝对值的一个非常明显的性质：

$|x|=\max\{x,-x\}$
非常明显，无须证明~

至于这个性质怎么用，后面自然就知道了 : )

如果我们选择 $(a,b)$ 位置上的山楂和 $(c,d)$ 位置上的柠檬，我们可以得到的酸度值是：

然后这意味着什么？

接下来就非常有意思了，我们不是要跑最大费用流嘛，如果我们把第 $i$ 堆山楂和第 $j$ 堆山楂之间连上 $4$ 条边：

那么跑最大费用流时肯定会流到最大的那一条，根据我们之前所说的性质，就是 $|x_i-x_j’|+|y_i-y_j’|$。

但是这样有什么用？连了 $4n^2$ 条边，比原来还连的多了！但是这 $4$ 个式子可以拆成分别只与 $\boldsymbol{i,j}$ 相关的两部分 ——

新建四个点 $a,b,c,d$，每堆山楂向 $a$ 连费用为 $x_i+y_i$ 的边、向 $b$ 连费用为 $x_i-y_i$ 的边、向 $c$ 连费用为 $-x_i+y_i$ 的边、向 $d$ 连 $-x_i-y_i$ 的边 …… 每堆柠檬同理。
那么只要流过点 $a$ ，费用就一定会构成式子：$x_i-x_j’+y_i-y_j’$……流过 $b,c,d$ 同理，分别对应四个式子。

所以边数就能减少到 $4n$ ，就可以过了~

Part4. 源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*Unlucky_Glass*/
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=1e3;
const ll inf=(1ll<<60);

struct GNODE{
	int to;
	ll cap,cst;
	GNODE *nxt,*rev;
	GNODE(){}
	GNODE(int _t,ll _ca,ll _cs,GNODE *_n,GNODE *_r):
		to(_t),cap(_ca),cst(_cs),nxt(_n),rev(_r){}
};
struct GRAPH{
	GNODE Gnod[(N*N+N+N)*2+10],*Gcnt,*Gtop[N*3];
	GRAPH(){Gcnt=Gnod;}
	void AddEdge(int u,int v,ll cap,ll cst){
		GNODE *p=++Gcnt,*q=++Gcnt;
		*p=GNODE(v,cap,cst,Gtop[u],q);Gtop[u]=p;
		*q=GNODE(u,0, -cst,Gtop[v],p);Gtop[v]=q;
	}
}Gflw;

GNODE *cop[N*3];
int n,Ps,Pt;
int Xa[N+3],Xb[N+3],Ya[N+3],Yb[N+3],Na[N+3],Nb[N+3];
ll dis[N*3];
bool inque[N*3];
bool vis[N*3];

ll fABS(ll Cx){return Cx<0? -Cx:Cx;}
pair<ll,ll> Aug(int u,ll flwin){
	if(u==Pt) return make_pair(flwin,0);
	ll flwout=0,totcst=0;
	vis[u]=true;
	for(GNODE *it=cop[u];it;it=it->nxt,cop[u]=cop[u]->nxt){
		int v=it->to;
		if(!it->cap || vis[v] || dis[v]!=dis[u]+it->cst) continue;
		ll flwv=min(flwin-flwout,it->cap);
		pair<ll,ll>resu=Aug(v,flwv);
		flwv=resu.first;
		totcst+=flwv*it->cst+resu.second;
		it->cap-=flwv;it->rev->cap+=flwv;
		flwout+=flwv;
		if(flwout==flwin) break;
	}
	vis[u]=false;
	return make_pair(flwout,totcst);
}
bool SPFA(){
	for(int i=1;i<=Pt;i++){
		dis[i]=-inf,cop[i]=Gflw.Gtop[i];
		inque[i]=vis[i]=false;
	}
	queue<int> que;
	que.push(Ps);
	dis[Ps]=0;inque[Ps]=true;
	while(!que.empty()){
		int u=que.front();que.pop();
		inque[u]=false;
		for(GNODE *it=cop[u];it;it=it->nxt){
			int v=it->to;
			if(!it->cap) continue;
			if(dis[u]+it->cst>dis[v]){
				dis[v]=dis[u]+it->cst;
//				if(v==Pt) return true;
				if(!inque[v]){
					inque[v]=true;
					que.push(v);
				}
			}
		}
	}
	return dis[Pt]!=-inf;
}
ll Dinic(){
	ll mxcst=0,mxflw=0;
	while(SPFA()){
		pair<ll,ll> resu=Aug(Ps,inf);
		mxflw+=resu.first;
		mxcst+=resu.second;
	}
	return mxcst;
}
int main(){
//	freopen("lemon.in","r",stdin);
//	freopen("lemon.out","w",stdout);
	scanf("%d",&n);
	Ps=n*2+5;Pt=n*2+6;
	for(int i=1;i<=n;i++) scanf("%d%d%d",&Xa[i],&Ya[i],&Na[i]);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&Xb[i],&Yb[i],&Nb[i]);
	for(int i=1;i<=n;i++){
		Gflw.AddEdge(i,2*n+1,inf,+Xa[i]+Ya[i]);
		Gflw.AddEdge(i,2*n+2,inf,+Xa[i]-Ya[i]);
		Gflw.AddEdge(i,2*n+3,inf,-Xa[i]+Ya[i]);
		Gflw.AddEdge(i,2*n+4,inf,-Xa[i]-Ya[i]);
		Gflw.AddEdge(2*n+1,i+n,inf,-Xb[i]-Yb[i]);
		Gflw.AddEdge(2*n+2,i+n,inf,-Xb[i]+Yb[i]);
		Gflw.AddEdge(2*n+3,i+n,inf,+Xb[i]-Yb[i]);
		Gflw.AddEdge(2*n+4,i+n,inf,+Xb[i]+Yb[i]);
	}
	for(int i=1;i<=n;i++)
		Gflw.AddEdge(Ps,i,Na[i],0ll),
		Gflw.AddEdge(i+n,Pt,Nb[i],0ll);
	printf("%lld\n",Dinic());
	return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com，欢迎提问~（你们说我是不是下次可以不写这个了……反正肯定没人会问）