您的位置: 首页  >  IT文章  >  [AGC034D]Manhattan Max Matching：费用流

[AGC034D]Manhattan Max Matching：费用流

分类: IT文章 • 2023-12-30 10:17:24

前置姿势

(k)维空间内两点曼哈顿距离中绝对值的处理

戳这里：[CF1093G]Multidimensional Queries

多路增广的费用流

据说这个东西叫做ZKW费用流？

流程其实很简单，就是把EK中的单路回溯改成利用DFS多路增广，类似Dinic那样，可以看作是EK的一个优化。需要注意的是要标记从源点到当前点的路径，以免陷入零环无法自拔。

代码

bool spfa(){
	memset(dis,0x3f,sizeof dis);
	rin(i,1,n)cur[i]=head[i];
	while(!q.empty())q.pop();
	dis[s]=0,book[s]=true;q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		trav(i,x){
			int ver=e[i].to;
			if(e[i].cap&&dis[ver]>dis[x]+e[i].cost){
				dis[ver]=dis[x]+e[i].cost;
				if(!book[ver]){
					book[ver]=true;
					q.push(ver);
				}
			}
		}
		book[x]=false;
	}
	return dis[t]<1e9;
}

int dfs(int x,int pref){
	if(x==t||!pref)return pref;
	int temp=0,flow=0;insta[x]=true;
	for(int &i=cur[x];i;i=e[i].nxt){
		int ver=e[i].to;if(insta[ver])continue;
		if(dis[ver]==dis[x]+e[i].cost&&(temp=dfs(ver,std::min(pref,e[i].cap)))){
			e[i].cap-=temp;
			e[i^1].cap+=temp;
			flow+=temp;
			pref-=temp;
			mincost+=temp*e[i].cost;
			if(!pref)break;
		}
	}
	insta[x]=false;
	return flow;
}

void ek(){
	while(spfa())maxflow+=dfs(s,1e9);
}

分析

显然费用流，直接建图的话每一对红球和蓝球（的位置）都需要连边，一共要连(O(N^2))条边，再跑费用流的话显然时间爆炸。

注意到把绝对值拆开后((x,y))系数只有(2^2)种可能性，并且两个球的距离是这四种情况中最大值，所以我们可以对四种情况分开处理，因为我们知道一对匹配的费用取的一定是最大值，即这两个球的距离。

具体如何建图可以参考代码。

代码

#include <bits/stdc++.h>

#define rin(i,a,b) for(int i=(a);i<=(b);++i)
#define irin(i,a,b) for(int i=(a);i>=(b);--i)
#define trav(i,a) for(int i=head[a];i;i=e[i].nxt)
#define Size(a) (int)a.size()
#define pb push_back
#define mkpr std::make_pair
#define fi first
#define se second
#define lowbit(a) ((a)&(-(a)))
typedef long long LL;

using std::cerr;
using std::endl;

inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=1005;

int n,s,t,ecnt=1,head[MAXN<<1];

struct Edge{
	int to,nxt,cap,cost;
}e[MAXN*20];

inline void add_edge(int bg,int ed,int ca,int co){
	++ecnt;
	e[ecnt].to=ed;
	e[ecnt].nxt=head[bg];
	e[ecnt].cap=ca;
	e[ecnt].cost=co;
	head[bg]=ecnt;
}

int maxflow,cur[MAXN<<1];
LL mincost,dis[MAXN<<1];
bool book[MAXN<<1],insta[MAXN<<1];
std::queue<int> q;

bool spfa(){
	memset(dis,0x3f,sizeof dis);
	rin(i,1,t)cur[i]=head[i];
	while(!q.empty())q.pop();
	dis[s]=0,book[s]=true;q.push(s);
	while(!q.empty()){
		int x=q.front();q.pop();
		trav(i,x){
			int ver=e[i].to;
			if(e[i].cap&&dis[ver]>dis[x]+e[i].cost){
				dis[ver]=dis[x]+e[i].cost;
				if(!book[ver]){
					book[ver]=true;
					q.push(ver);
				}
			}
		}
		book[x]=false;
	}
	return dis[t]<1e18;
}

int dfs(int x,int pref){
	if(x==t||!pref)return pref;
	int temp=0,flow=0;insta[x]=true;
	for(int &i=cur[x];i;i=e[i].nxt){
		int ver=e[i].to;if(insta[ver])continue;
		if(dis[ver]==dis[x]+e[i].cost&&(temp=dfs(ver,std::min(pref,e[i].cap)))){
			e[i].cap-=temp;
			e[i^1].cap+=temp;
			flow+=temp;
			pref-=temp;
			mincost+=1ll*temp*e[i].cost;
			if(!pref)break;
		}
	}
	insta[x]=false;
	return flow;
}

void ek(){
	while(spfa())maxflow+=dfs(s,1e9);
}

int main(){
	n=read();
	int x0=n*2+1,x1=x0+1,x2=x1+1,x3=x2+1;
	s=x3+1,t=s+1;
	rin(i,1,n){
		int rx=read(),ry=read(),rc=read();
		add_edge(s,i,rc,0);
		add_edge(i,s,0,0);
		add_edge(i,x0,1e9,rx+ry);
		add_edge(x0,i,0,-rx-ry);
		add_edge(i,x1,1e9,rx-ry);
		add_edge(x1,i,0,-rx+ry);
		add_edge(i,x2,1e9,-rx+ry);
		add_edge(x2,i,0,rx-ry);
		add_edge(i,x3,1e9,-rx-ry);
		add_edge(x3,i,0,rx+ry);
	}
	rin(i,1,n){
		int bx=read(),by=read(),bc=read();
		add_edge(n+i,t,bc,0);
		add_edge(t,n+i,0,0);
		add_edge(x0,n+i,1e9,-bx-by);
		add_edge(n+i,x0,0,bx+by);
		add_edge(x1,n+i,1e9,-bx+by);
		add_edge(n+i,x1,0,bx-by);
		add_edge(x2,n+i,1e9,bx-by);
		add_edge(n+i,x2,0,-bx+by);
		add_edge(x3,n+i,1e9,bx+by);
		add_edge(n+i,x3,0,-bx-by);
	}
	ek();
	printf("%lld
",-mincost);
	return 0;
}

相关推荐