题解 AGC034D【Manhattan Max Matching】

problem

在一个二维坐标系内，点 $(RX_i,RY_i)$ 上有 $RC_i$ 个红球，点 $(BX_i,BY_i)$ 上有 $BC_i$ 个蓝球，且保证 $\sum_{i=1}^{n}RC_i=\sum_{i=1}^{n}BC_i$。

现在要你将这些红球蓝球一一配对，配对的价值为两球所在点之间的曼哈顿距离，请你求出配对完它们的最大价值和。

$ \xcancel{1\ \leq\ N\ \leq\ 1000 }\to \sum_{i=1}^{N}\ RC_i \leq 10^5$
$ 0\ \leq\ RX_i,RY_i,BX_i,BY_i\ \leq\ 10^9 $
$ 1\ \leq\ RC_i,BC_i\ \leq\ 10 $
$ \sum_{i=1}^{N} RC_i=\sum_{i=1}^{N}BC_i $
入力される値はすべて整数である。

solution 0

考虑费用流，因为我们观察到如下事实：

\[\begin{aligned} \lvert a - b \rvert &= \max(a - b, b - a)\\ \max(a, b) + \max(c, d) &= \max(a + c, a + d, b + c, b + d)\\ \implies\max(|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) \end{aligned} \]

也就是说这个曼哈顿距离可以转化为四种情况取 $\max$。由于这题恰好也是最大，所以直接最大费用最大流即可，中间四个点，两边连边，连边费用是 $\pm x\pm y$ 之类的东西，然后要有四个点（下文称作【颜色】）的区分。

solution 1

因为原图流量上限都为 $1$，考虑模拟费用流，首先先声明这个图是没有正环的，因此增广路不应该经过重复点，我们先声明这个事实。

考虑一条增广路的走法，它总是形如：

先从源点经过一个球走到一个颜色 $u$。
从 $u$ 出发兜兜转转，做一堆反悔，到达颜色 $v$。
从 $v$ 出发经过一个球走到汇点。

举个例子，这个增广路可能是这样扭曲的：

可以看到这里 $u=1, v = 0$。中间增广路可以经过左部点，可以经过右部点，但关键是增广路长度是 $O(\text{颜色数})$ 的（颜色数），也就是说我们也许可以大力找出增广路去增广，而不是每一次都 spfa。

typedef priority_queue<pair<LL, int>> pqueue。

我们开很多个 pqueue qm[2][4], qf[2][4][4]，分别表示：

qm[0][u] 表示左部点未匹配的点，到达颜色 $u$ 的费用的一个集合，就是形如 $\{(w_L(x,u), x):x\in unmatched\}$ 的集合，其中 $w_L(x, u)$ 是左部点 $x$ 到颜色 $u$ 的费用，的边权。qm[1][v] 就是右部点了。
qf[0][u][v] 表示只考虑左部点决策，可以将匹配颜色 $u$ 反悔成 $v$ 的集合，形式化的：
- $\{(w_L(x, v)-w_L(x, u), x): match_x=u\}$
这里有必要给一下 qf[1][u][v] 的形式化定义，它的增广方向是反过来的：
- $\{(w_R(y, u)-w_R(y, v), y): match_y=v\}$

那么考虑增广路是怎么走的：

先从源点经过一个球走到一个颜色 $u$。拿出 qm[0][u].top()，注意你可能需要懒惰删除一下，把已经不在集合中的决策删掉。
从 $u$ 出发兜兜转转，做一堆反悔，到达颜色 $v$。
- 可以枚举所有可能的路径，取出 max(qf[0][u][v], qf[1][u][v]) 作为一次反悔的边权。注意懒惰删除。
- 也可以取 max(qf[0][u][v], qf[1][u][v]) 作为边权，跑 floyd 最长路，同时记录路径，利于以后反悔。
从 $v$ 出发经过一个球走到汇点。拿出 qm[1][v].top()，同样懒惰删除。

然后跑这条增广路，只需要更新一下沿途走过的颜色产生的新的决策，加入 pqueue 中。

复杂度大约是 $O(n\log n)$ 的，但是这个常数有点逆天，可能最多是 $4^3$ 吧？跑得很快很快。

code

费用流

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <queue>
#include <functional>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
#define x first
#define y second
typedef long long LL;
//template<int N> struct flower{
//    int b[N+10],cnt;
//    flower():cnt(0){}
//    void operator+=(int x){b[++cnt]=x;}
//    void build(){sort(b+1,b+cnt+1),cnt=unique(b+1,b+cnt+1)-b-1;}
//    int operator()(int x){return lower_bound(b+1,b+cnt+1,x)-b;}
//    int operator[](int i){return b[i];}
//};
template<int N,int M,class T=int> struct graph{
    int head[N+10],nxt[M*2+10],cnt,tot;
    struct edge{
        int u,v;T w;
        edge(int u=0,int v=0,T w={0,0}):u(u),v(v),w(w){}
    } e[M*2+10];
    graph(){memset(head,tot=cnt=0,sizeof head);}
    edge& operator[](int i){return e[i];}
    void add(int u,int v,T w){e[++cnt]=edge(u,v,w),nxt[cnt]=head[u],head[u]=cnt;}
    void link(int u,int v,T w){add(u,v,w),add(v,u,w);}
};
template<int N,int M,class T=int,class F=int> struct mcmf_g:public graph<N,M,pair<T,F>>{
	graph<N,M,pair<T,F>>&g=*this;
	mcmf_g(){g.add(0,0,{0,0});}
	void insert(int u,int v,T w,F c){debug("insert(%d,%d,%d,%d)\n",u,v,w,c),g.add(u,v,{w,c}),g.add(v,u,{0,-c});}
	F dis[N+10]; int cur[N+10],vis[N+10];
	bool bfs(int s,int t){
		queue<int> q; memset(dis,0x3f,sizeof dis),memset(vis,0,sizeof vis);
		for(q.push(s),dis[s]=0;!q.empty();){
			int u=q.front(); q.pop(),vis[u]=0;
			for(int i=g.head[u];i;i=g.nxt[i]){
				int v=g[i].v; if(!g[i].w.first) continue;
				if(dis[v]>dis[u]+g[i].w.second) dis[v]=dis[u]+g[i].w.second,!vis[v]&&(q.push(v),vis[v]=1);
			}
		}
		return dis[t]!=dis[0];
	}
	T dfs(int u,T flow,int t){
		if(u==t||!flow) return flow;
		T rest=flow; vis[u]=1;
		for(int &i=cur[u];i;i=g.nxt[i]){
			int v=g[i].v; if(dis[v]!=dis[u]+g[i].w.second||vis[v]||!g[i].w.first) continue;
			T run=dfs(v,min(rest,g[i].w.first),t);
			if(g[i].w.first-=run,g[i^1].w.first+=run,!(rest-=run)) break;
		}
		if(rest==flow) vis[u]=0; return flow-rest;
	}
	pair<T,F> mcmf(int s,int t,T inf){
		pair<T,F> flow={0,0};
		while(bfs(s,t)){
			memcpy(cur,g.head,sizeof cur);
			T run=dfs(s,inf,t); flow.first+=run,flow.second+=run*dis[t];
		}
		return flow;
	}
};
mcmf_g<10010,20010,LL,LL> g;
int n,rcnt[1010],bcnt[1010],rid[1010],bid[1010],id[2010],S=++g.tot,T=++g.tot;
pair<int,int> rd[1010],bd[1010];
//flower<2010> b;
//void work(function<int(pair<int,int>)> calc){
//	b.cnt=0;
//	for(int i=1;i<=n;i++) b+=calc(rd[i]),b+=calc(bd[i]);
//	b.build();
//	for(int i=1;i<=b.cnt;i++) id[i]=++g.tot;
//	for(int i=1;i<b.cnt;i++) g.insert(id[i],id[i+1],1e9,-(b[i+1]-b[i]));
//	for(int i=1;i<=n;i++) g.insert(rid[i],id[b(calc(rd[i]))],1e9,0);
//	for(int i=1;i<=n;i++) g.insert(id[b(calc(bd[i]))],bid[i],1e9,0);
//	for(int i=1;i<=b.cnt;i++) id[i]=++g.tot;
//	for(int i=1;i<b.cnt;i++) g.insert(id[i+1],id[i],1e9,-(b[i+1]-b[i]));
//	for(int i=1;i<=n;i++) g.insert(rid[i],id[b(calc(rd[i]))],1e9,0);
//	for(int i=1;i<=n;i++) g.insert(id[b(calc(bd[i]))],bid[i],1e9,0);
//}
int main(){
//	#ifdef LOCAL
//		freopen("input.in","r",stdin);
//	#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&rd[i].x,&rd[i].y,&rcnt[i]),g.insert(S,rid[i]=++g.tot,rcnt[i],0);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&bd[i].x,&bd[i].y,&bcnt[i]),g.insert(bid[i]=++g.tot,T,bcnt[i],0);
//	work([](pair<int,int> a)->int{return a.x+a.y;});
//	work([](pair<int,int> a)->int{return a.x-a.y;});
	int ps[]={++g.tot,++g.tot,++g.tot,++g.tot};
	for(int i=1;i<=n;i++){
		g.insert(rid[i],ps[0],1e9,+rd[i].x+rd[i].y);
		g.insert(rid[i],ps[1],1e9,+rd[i].x-rd[i].y);
		g.insert(rid[i],ps[2],1e9,-rd[i].x-rd[i].y);
		g.insert(rid[i],ps[3],1e9,-rd[i].x+rd[i].y);
		g.insert(ps[0],bid[i],1e9,-bd[i].x-bd[i].y);
		g.insert(ps[1],bid[i],1e9,-bd[i].x+bd[i].y);
		g.insert(ps[2],bid[i],1e9,+bd[i].x+bd[i].y);
		g.insert(ps[3],bid[i],1e9,+bd[i].x-bd[i].y);
	}
	debug("orz");
	printf("%lld\n",-g.mcmf(S,T,1e18).second);
	return 0;
}

模拟费用流

// ubsan: undefined
// accoders
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <queue>
#include <tuple>
#include <vector>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
typedef priority_queue<pair<LL, int>> pqueue;
int n;
LL w[2][100010][4];
pqueue qf[2][4][4], qm[2][4];
// qf 正在等待反悔，原来是 u 可以返回成 v
// qm 是等待匹配这个颜色
vector<int> path[4][4];
LL dis[4][4];
bool typ[4][4];  // typ[u][v] 表示 u->v 这条边是通过左边还有右边过去的
int mch[2][100010];  // mch[u] 表示匹配了谁
bool check(int d, int u, pqueue &q) {
  while (!q.empty() && mch[d][q.top().second] != u) q.pop();
  return !q.empty();
}
void updmch(int d, int p) {
  if (d == 0) {
    int x = p, u = mch[0][x];
    for (int c = 0; c < 4; c++)
      if (u != c) qf[0][u][c].emplace(w[0][x][c] - w[0][x][u], x);
  } else {
    int y = p, v = mch[1][y];
    for (int c = 0; c < 4; c++)
      if (c != v) qf[1][c][v].emplace(w[1][y][c] - w[1][y][v], y);
  }
}
LL flow() {
  for (int u = 0; u < 4; u++)
    for (int v = 0; v < 4; v++)
      if (u != v) {
        dis[u][v] = -1e18;
        path[u][v] = {u, v};
        for (int d : {0, 1})
          if (check(d, d ? v : u, qf[d][u][v]))
            if (qf[d][u][v].top().first > dis[u][v]) {
              dis[u][v] = qf[d][u][v].top().first;
              typ[u][v] = d;
            }
      } else {
        dis[u][v] = 0;
        path[u][v] = {u};
      }
  for (int k = 0; k < 4; k++)
    for (int u = 0; u < 4; u++)
      for (int v = 0; v < 4; v++)
        if (dis[u][v] < dis[u][k] + dis[k][v]) {
          dis[u][v] = dis[u][k] + dis[k][v];
          path[u][v] = path[u][k];
          path[u][v].pop_back();
          path[u][v].insert(path[u][v].end(), path[k][v].begin(),
                            path[k][v].end());
        }
  LL maxf = -1e18;
  int au = 0, av = 0;
  for (int u = 0; u < 4; u++)
    for (int v = 0; v < 4; v++)
      if (check(0, -1, qm[0][u]) && check(1, -1, qm[1][v])) {
        LL left = qm[0][u].top().first, right = qm[1][v].top().first;
        debug("qm[0][%d] = %lld, qm[1][%d] = %lld, dis[%d][%d] = %lld\n", u,
              left, v, right, u, v, dis[u][v]);
        if (maxf < left + right + dis[u][v]) {
          maxf = left + right + dis[u][v];
          tie(au, av) = make_pair(u, v);
        }
      }
#ifdef LOCAL
  debug("path = ");
  for (int x : path[au][av]) debug("%d, ", x);
  debug("\n");
#endif
  if (au != av) {
    for (int i = 0; i + 1 < path[au][av].size(); i++) {
      int u = path[au][av][i], v = path[au][av][i + 1];
      if (!typ[u][v]) {
        int x = qf[0][u][v].top().second;
        assert(mch[0][x] == u);
        mch[0][x] = v;
        updmch(0, x);
      } else {
        int y = qf[1][u][v].top().second;
        assert(mch[1][y] == v);
        mch[1][y] = u;
        updmch(1, y);
      }
    }
  }
  debug("maxf = %lld\n", maxf);
  int x = qm[0][au].top().second;
  mch[0][x] = au;
  updmch(0, x);
  int y = qm[1][av].top().second;
  mch[1][y] = av;
  updmch(1, y);
  return maxf;
}
int main() {
#ifndef NF
  freopen("match.in", "r", stdin);
  freopen("match.out", "w", stdout);
#endif
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    LL x, y;
    scanf("%lld%lld", &x, &y);
    for (int p : {0, 1})
      for (int q : {0, 1})
        w[0][i][p * 2 + q] = x * (p ? -1 : 1) + y * (q ? -1 : 1);
  }
  for (int i = 1; i <= n; i++) {
    LL x, y;
    scanf("%lld%lld", &x, &y);
    for (int p : {0, 1})
      for (int q : {0, 1})
        w[1][i][!p * 2 + !q] = x * (p ? -1 : 1) + y * (q ? -1 : 1);
  }
  memset(mch, -1, sizeof mch);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 4; j++) {
      qm[0][j].emplace(w[0][i][j], i);
      qm[1][j].emplace(w[1][i][j], i);
    }
  }
  LL ans = 0;
  for (int i = 1; i <= n; i++) ans += flow();
  printf("%lld\n", ans);
  return 0;
}