OI - Manhattan Max Matching (AtCoder)

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


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,欢迎提问~(你们说我是不是下次可以不写这个了……反正肯定没人会问)

0%