「AGC034D」 Manhattan Max Matching

不知道这个结论啊。。。

（其实就是菜嘛）

首先 \(O(n^2)\) 的建边显然不太行。

曼哈顿距离有这样一个性质，如果将绝对值符号拆掉，曼哈顿距离的值一定是所有情况的最大值。

然后根据这个性质我们可以把点拆成四种 \((\pm x,\pm y)\)，然后连边直接跑最大流就完事了。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

typedef long long ll;

struct edge{

	ll to,nex,w,v;

}e[maxn*20];

int head[maxn],cur[maxn],cnt=1;

int n,m,s,t;

void add(ll a,ll b,ll c,ll d){

	e[++cnt]=(edge){b,head[a],c,d};

	head[a]=cnt;

}

void addedge(ll a,ll b,ll c,ll d){

	add(a,b,c,d),add(b,a,0,-d);

}

ll dis[maxn],vis[maxn];

bool spfa(){

	for(int i=s;i<=t;++i) dis[i]=-(1ll<<60),cur[i]=head[i];

	queue<int> Q;

	dis[s]=0,vis[s]=1,Q.emplace(s);

	while(!Q.empty()){

		ll u=Q.front();Q.pop();

		vis[u]=0;

		for(int i=head[u];i;i=e[i].nex){

			int v=e[i].to;

			if(e[i].w&&dis[v]<dis[u]+e[i].v){

				dis[v]=dis[u]+e[i].v;

				if(!vis[v]) vis[v]=1,Q.emplace(v);

			}

		}

	}

	return dis[t]>-(1ll<<60);

}

ll dfs(int u,ll in){

	if(u==t) return in;

	ll out=0,tmp;

	vis[u]=1;

	for(int i=cur[u];i;i=e[i].nex){

		cur[u]=i;

		int v=e[i].to;

		if((!vis[v])&&e[i].w&&dis[v]==dis[u]+e[i].v&&(tmp=dfs(v,min(e[i].w,in)))){

			in-=tmp,out+=tmp;

			e[i].w-=tmp,e[i^1].w+=tmp;

			if(!in) break;

		}

	}

	if(!out) dis[u]=0;

	vis[u]=0;

	return out;

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	cin>>n;

	int p1=2*n+1,p2=2*n+2,p3=2*n+3,p4=2*n+4;

	s=0,t=2*n+5;

	for(int i=1;i<=n;++i){

		int x,y,c;cin>>x>>y>>c;

		addedge(s,i,c,0);

		addedge(i,p1,c,x+y);

		addedge(i,p2,c,x-y);

		addedge(i,p3,c,-x+y);

		addedge(i,p4,c,-x-y);

	}

	for(int i=1;i<=n;++i){

		int x,y,c;cin>>x>>y>>c;

		addedge(i+n,t,c,0);

		addedge(p1,i+n,c,-x-y);

		addedge(p2,i+n,c,-x+y);

		addedge(p3,i+n,c,x-y);

		addedge(p4,i+n,c,x+y);

	}

	ll ans=0;

	while(spfa()){

		ll tmp=dfs(s,1e9);

		ans-=tmp*dis[t];

	}

	cout<<-ans<<'\n';

	return 0;

}

巴特西

「AGC034D」 Manhattan Max Matching

「AGC034D」 Manhattan Max Matching

最新文章

热门文章