题解 AT4994 【[AGC034D] Manhattan Max Matching】

· · 题解

首先显然可以想到暴力建出二分图之后跑费用流，但是边数有O(n^2)条，比较爆炸，考虑优化。

可以发现，曼哈顿距离有一个非常好的性质，就是把绝对值拆开，一共有四种情况，这四种情况的最大值一定是这个曼哈顿距离的值。

具体地说，就是：

|x_1-x_2|+|y_1-y_2|=max\{ x_1-x_2+y_1-y_2, x_1-x_2-y_1+y_2, -x_1+x_2+y_1-y_2, -x_1+x_2-y_1+y_2 \}

那么可以将两个点独立地来看，也就是：

|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), (-x_1+y_1)+(x_2-y_2), (-x_1-y_1)+(x_2+y_2) \}

那么既然可以拆开来看的话，就可以不用两两连边了，在左右两排点中间开4个新点，然后从左边到它，从它到左边分别连上4种边（记得按顺序），然后直接跑费用流即可，边数被降到O(n)级别、

但是需要注意的是，曼哈顿距离这个性质不适用于最小值。

code：

#include<bits/stdc++.h>
#define maxn 1010
#define inf 1000000007
using namespace std;
typedef long long ll;
int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch-'0'<0||ch-'0'>9){if(ch=='-') f=-1;ch=getchar();}
    while(ch-'0'>=0&&ch-'0'<=9){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,p1,p2,p3,p4,s,t;
int head[maxn*2],nxt[maxn*20],to[maxn*20],c[maxn*20],v[maxn*20],tot=1;
void add(int x,int y,int z,int u)
{
    ++tot;
    nxt[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
    c[tot]=z;
    v[tot]=u;
}
void addx(int x,int y,int z,int u)
{
    add(x,y,z,u);
    add(y,x,0,-u);
}
ll ans;
ll dis[maxn*2];
int pre[maxn*2],pre_num[maxn*2],vis[maxn*2];
queue<int>q;
int spfa()
{
    for(int i=1;i<=t;i++)  dis[i]=-1e16;
    q.push(s);dis[s]=0;vis[s]=1;
    while(q.size())
    {
        int now=q.front();q.pop();vis[now]=0;
        for(int i=head[now];i;i=nxt[i])
        {
            if(dis[to[i]]<dis[now]+v[i]&&c[i])
            {
                dis[to[i]]=dis[now]+v[i];
                pre[to[i]]=now;
                pre_num[to[i]]=i;
                if(!vis[to[i]])  q.push(to[i]),vis[to[i]]=1;
            }
        }
    }
    if(dis[t]==-1e16)  return 0;
    int di=inf;
    for(int i=t;i!=s;i=pre[i])  di=min(di,c[pre_num[i]]);
    for(int i=t;i!=s;i=pre[i])  c[pre_num[i]]-=di,c[pre_num[i]^1]+=di;
    ans+=dis[t]*di;
    return di;
}
int main()
{
    n=read();p1=2*n+1;p2=p1+1;p3=p2+1;p4=p3+1;s=p4+1;t=s+1;
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),z=read();
        addx(s,i,z,0);
        addx(i,p1,inf,x+y);
        addx(i,p2,inf,x-y);
        addx(i,p3,inf,-x+y);
        addx(i,p4,inf,-x-y);
    }
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read(),z=read();
        addx(i+n,t,z,0);
        addx(p1,i+n,inf,-x-y);
        addx(p2,i+n,inf,-x+y);
        addx(p3,i+n,inf,x-y);
        addx(p4,i+n,inf,x+y);
    }
    while(spfa()){};
    printf("%lld\n",ans);
    return 0;
}