[AGC034D]Manhattan Max Matching：费用流

前置姿势

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

多路增广的费用流

据说这个东西叫做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\n",-mincost);

	return 0;

}

巴特西

[AGC034D]Manhattan Max Matching：费用流

前置姿势

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

多路增广的费用流

代码

分析

代码

最新文章

热门文章