(Atcoder-AGC034D)Manhattan Max Matching

题目

Atcoder
有一个无限大的平面，有 $2n$ 个位置上面有若干个球（可能重复），其中N个位置是红球，N个位置是蓝球，红球与蓝球的总数均为 $s$。
给出 $2n$ 个位置和上面的球数，现要将红球与蓝球完美匹配，匹配的权值是每一对匹配两个球的位置坐标的曼哈顿距离之和，求最大权值。
$n\le 1000$，每个位置上球数 $c_i\le 10$，$1\le x_i,y_i\le 10^9$

思路

思路非常巧妙
首先我们可以考虑两两连边跑费用流，但是边数是 $O(n^2)$ 的，会TLE
考虑优化建图
我们知道曼哈顿距离是这样的：
$di{s}_{ij}=|x_i?x_j|+|y_i?y_j|$
考虑将 $di{s}_{ij}$
$$\begin{gathered} di{s}_{ij}=|x_i?x_j|+|y_i?y_j|= \\ max(x_i+y_i?x_j?y_j,x_i?y_i?x_j+y_j,?x_i+y_i+x_j?y_j,?x_i?y_i+x_j+y_j) \end{gathered}$$
我们知道，合法的情况一定是最大的，而这上面四种情况描述的两个点的相对关系
两个点的相对关系有4种，于是我们分类连边即可
因为又是最大费用，那么跑出来的一定是答案
(如果求最小权值还不能这样做，因为不一定对应合法情况),这样就是 $O(n)$ 的建边，可过。

代码

#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
int read(){
    int f=0,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?-x:x;
}
#define MAXN 5000
#define MAXM 100000
#define INF 0x3f3f3f3f
struct Edge{
    int nxt,v,cap,w;
}edge[MAXM+5];
int ncnt=-1,head[MAXN+5];
void Addedge(int u,int v,int cap,int w){
    edge[++ncnt]=(Edge){
    head[u],v,cap,w},head[u]=ncnt;edge[++ncnt]=(Edge){
    head[v],u,0,-w},head[v]=ncnt;return ;
}
int N,S,T;
bool vis[MAXN+5];
int cur[MAXN+5];
LL dep[MAXN+5];
bool BFS(){
    queue<int> Q;for(int i=0;i<=N;i++)vis[i]=0,dep[i]=1ll*10000*INF;dep[S]=0,vis[S]=1,Q.push(S);while(!Q.empty()){
    int u=Q.front();Q.pop();vis[u]=0;for(int i=head[u];~i;i=edge[i].nxt){
    int v=edge[i].v,cap=edge[i].cap,w=edge[i].w;if(cap&&dep[v]>dep[u]+w){
    dep[v]=dep[u]+w;if(!vis[v])vis[v]=1,Q.push(v);}}}return dep[T]<1ll*10000*INF;
}
LL cost;
int DFS(int u,int aug){
    if(u==T) return aug;vis[u]=1;int flow=0,f;for(int i=cur[u];i!=-1;i=edge[i].nxt){
    cur[u]=i;int v=edge[i].v,cap=edge[i].cap,w=edge[i].w;if(!vis[v]&&dep[v]==dep[u]+w&&cap&&(f=DFS(v,min(cap,aug)))){
    aug-=f,flow+=f,cost+=1ll*f*w;edge[i].cap-=f,edge[i^1].cap+=f;if(!aug) break;}}vis[u]=0;return flow;
}
#define Flow 0x3f3f3f3f
void Dinic(){
    //int Max_Flow=0;while(BFS())memcpy(cur,head,sizeof(head)),DFS(S,Flow);return ;
}
int main(){
    memset(head,-1,sizeof(head));int n=read();N=2*n+6,S=2*n+1,T=2*n+2;int n1=2*n+3,n2=2*n+4,n3=2*n+5,n4=2*n+6;for(int i=1;i<=n;i++){
    int x=read(),y=read(),c=read();Addedge(S,i,c,0);Addedge(i,n1,INF,-x-y);Addedge(i,n2,INF,-x+y);Addedge(i,n3,INF,x-y);Addedge(i,n4,INF,x+y);}for(int i=1;i<=n;i++){
    int x=read(),y=read(),c=read();Addedge(n+i,T,c,0);Addedge(n1,n+i,INF,x+y);Addedge(n2,n+i,INF,x-y);Addedge(n3,n+i,INF,-x+y);Addedge(n4,n+i,INF,-x-y);}Dinic();printf("%lld\n",-cost);return 0;
}

思考

还是那句话，网络流的题要多做才能有建图技巧