AtCoder agc_034D - Manhattan Max Matching（最大费用最大流）

AtCoder agc_034D - Manhattan Max Matching

题目大意

• 平面上有$N$个位置上分别有若干红点，$N$个位置上分别有若干蓝点，保证红点蓝点总数相等。
• 求一个红点和蓝点的匹配，使得每个点对的曼哈顿距离之和最大，输出最小的答案。
• $N\le 1000$

题解

• 据说奇奇怪怪限制的题，一般会想到网络流，
• 这题还有关点对之间的匹配，则更像是网络流。
• 观察题目的限制，不同的匹配权值不同，考虑使用费用流，即最大费用最大流。
• 由于曼哈顿距离的式子中有绝对值，先把绝对值拆开，会出现四种情况，分别是$(x_i?x_j)+(y_i?y_j)$、$(x_i?x_j)+(y_j?y_i)$、$(x_j?x_i)+(y_i?y_j)$、$(x_j?x_i)+(y_j?y_i)$,
• • 先从源点连向每个红点的位置（简称为红点），费用为$0$，容量为这个位置上的点数；每个蓝点连向汇点同理，
• 接着上述四种情况对应另外新设的四个点，每个红点往这四个点连边，容量正无穷，费用为这个点的代表的式子中$x_i$和$x_j$分别对应的正负之和，这四个点再连向蓝点，边权同理。
• 但是会发现，这样能保证流出的费用正好是曼哈顿距离吗？如果一对匹配不是恰好在大减小的位置流过，那不就错了吗？
• 其实会发现，因为题目求的是最大费用，而加上绝对值一定是大于等于没有绝对值的，所以最终流过去的方案必然会是曼哈顿距离，且必为最优解。
• 至于最大费用最大流，只需要把费用流SPFA中的最短路改成最长路即可。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1010
#define ll long long
int last[N*2],cur[N*2],len=1;
ll dis[N*2];
int q[N*2],p[N*2];
ll ans=0;
struct
{
    int c,w,to,next;
}a[N*20];
int n,ns,m;
void add(int x,int y,int c,int w)
{
    a[++len].to=y;a[len].next=last[x];a[len].c=c,a[len].w=w;last[x]=len;
}
int id = 0;
int SPFA()
{
    for(int i=0;i<=ns;i++) dis[i]=-1e16;q[1]=0,p[0]=++id,dis[0]=0;int l=0,r=1;while(l!=r){
    l=l%(ns+10)+1;int k=q[l];p[k]=0;for(int i=last[k];i;i=a[i].next) {
    int x=a[i].to;if(dis[k]+a[i].w>dis[x]&&a[i].c){
    dis[x]=dis[k]+a[i].w;if(p[x] < id){
    p[x]=id;r=r%(ns+10)+1;q[r]=x;}}}}return dis[ns]>0;
}
int dfs(int k,int flow)
{
    if(k==ns) return flow;int have=0;p[k]=1;for(int i=cur[k];i;i=a[i].next){
    int x=a[i].to;if(!p[x]&&dis[k]+a[i].w==dis[x]&&a[i].c){
    cur[k] = i;int t=min(flow-have,a[i].c);int now=dfs(x,t);ans+=(ll)now*a[i].w;have+=now,a[i].c-=now,a[i^1].c+=now;if(have==flow) break;}}p[k]=0;return have;
}
int main()
{
    int i,x,y,c;scanf("%d",&n);for(i=1;i<=n;i++){
    scanf("%d%d%d",&x,&y,&c);add(i,2*n+1,c,x+y);add(2*n+1,i,0,-x-y);add(i,2*n+2,c,x-y);add(2*n+2,i,0,y-x);add(i,2*n+3,c,y-x);add(2*n+3,i,0,x-y);add(i,2*n+4,c,-x-y);add(2*n+4,i,0,x+y);add(0,i,c,0);add(i,0,0,0);}for(i=1;i<=n;i++){
    scanf("%d%d%d",&x,&y,&c);add(2*n+1,i+n,1e6,-x-y);add(i+n,2*n+1,0,x+y);add(2*n+2,i+n,1e6,y-x);add(i+n,2*n+2,0,x-y);add(2*n+3,i+n,1e6,x-y);add(i+n,2*n+3,0,y-x);add(2*n+4,i+n,1e6,x+y);add(i+n,2*n+4,0,-x-y);add(i+n,2*n+5,c,0);add(2*n+5,i+n,0,0);}ns=2*n+5;while(SPFA()){
    while(1) {
    for(i = 0; i <= ns; i++) cur[i] = last[i];int t = dfs(0,1e6);	if(!t) break;}}printf("%lld",ans);return 0;
}