题解：P12463 [Ynoi Easy Round 2018] 星野瑠美衣

下面认为

x_{n+1}=x_1,y_{n+1}=y_1

以及

n,m

同阶。

先来研究

y

全部相等的情况。

数轴上我们把权值为

v

的

x

插入到

x_1,x_2

之间，则总权值有如下几种变化量：

当 $x<\min\{x_1,x_2\}$ ，变化量为 $-|x_1-x_2|+x_1+x_2-2x+v$ ；
当 $\min\{x_1,x_2\}\le x\le \max\{x_1,x_2\}$ ，变化量为 $v$ ；
当 $x>\max\{x_1,x_2\}$ ，变化量为 $-|x_1-x_2|-x_1-x_2+2x+v$ 。

画图发现，我们可以不管前提条件，直接对这三个式子取

\max

就可以得到最大值。

再加上

y

的贡献，一共就是

9

种情况。

那么就可以进行费用流建模了。

我们一共有五类点：源点

S

、汇点

T

、代表

m

个点的

A_1,\cdots,A_m

、代表可插入的

n

个空位的

B_1,\cdots,B_n

、计算权值的虚点

C_1,\cdots,C_9

。

有如下四类容量均为

1

的边：

$S$ 连向 $A_i$ ，费用为 $v_i$ 。
$B_i$ 连向 $T$ ，费用为 $-|x_i-x_{i+1}|-|y_i-y_{i+1}|$ 。
$A_i$ 连向 $C_j$ ，费用为 $C_j$ 所对应的连边方式中属于插入点的贡献，即 $-2x,0,2x$ 之一加上 $-2y,0,2y$ 之一。
$C_j$ 连向 $B_i$ ，费用为 $C_j$ 所对应的连边方式中属于插入空位的贡献，即 $x_i+x_{i+1},0,-x_i-x_{i+1}$ 之一加上 $y_i+y_{i+1},0,-y_i-y_{i+1}$ 之一。

点数边数都是

O(n)

，没有正环。直接跑最大费用最大流即可，时间复杂度

O(n^3)

。

直接费用流跑不过去，考虑模拟费用流，我们每次找一条增广路。

这张图是二分图，左部点有

S,T,C_1,\cdots,C_9

一共

11

个，剩下的是右部点。增广时我们会找一条从

S

到

T

的路径，由于是二分图，路径必然是左部点右部点交错，因此长度是

O(1)

的。

那么直接维护任意两个左部点之间经过一个右部点的最长路，以这个为边权在左部点内部跑 SPFA，找出来增广路后暴力修改影响到的路径。我们维护任意两个左部点之间经过一个右部点的所有路径，每次增广是把

O(1)

条边反转了，相当于是删除

O(1)

条路径再加入

O(1)

条，使用可删堆维护即可。

时间复杂度

O(n\log n)

。

代码

CPP

#include<bits/stdc++.h>
#define File(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define ll long long
#define F(i,a,b) for(int i(a),i##i##end(b);i<=i##i##end;++i)
#define R(i,a,b) for(int i(a),i##i##end(b);i>=i##i##end;--i)
#define fi first
#define se second
using namespace std;
const int MAXN=2e5+1;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,m,px[MAXN],py[MAXN],x[MAXN],y[MAXN],v[MAXN];
//S->0,T->10
priority_queue<pair<ll,int> >q[11][11],del[11][11];
ll ans,val[11][MAXN],dis[11][11],dep[11];
int dir[11][MAXN],fr[11];
inline void era(int u,int mid,int v){
	F(i,0,10) if(dir[i][mid]*dir[u][mid]==-1){
		if(dir[u][mid]==1) del[u][i].emplace(val[u][mid]+val[i][mid],mid);
		else del[i][u].emplace(val[u][mid]+val[i][mid],mid);
	}
	F(i,0,10) if(i!=u&&dir[i][mid]*dir[v][mid]==-1){
		if(dir[v][mid]==-1) del[i][v].emplace(val[v][mid]+val[i][mid],mid);
		else del[v][i].emplace(val[v][mid]+val[i][mid],mid);
	}
}
inline void add(int u,int mid,int v){
	F(i,0,10) if(dir[i][mid]*dir[v][mid]==-1){
		if(dir[v][mid]==1) q[v][i].emplace(val[v][mid]+val[i][mid],mid);
		else q[i][v].emplace(val[v][mid]+val[i][mid],mid);
	}
	F(i,0,10) if(i!=v&&dir[i][mid]*dir[u][mid]==-1){
		if(dir[u][mid]==-1) q[i][u].emplace(val[u][mid]+val[i][mid],mid);
		else q[u][i].emplace(val[u][mid]+val[i][mid],mid);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	F(i,1,n) cin>>px[i]>>py[i];
	px[n+1]=px[1],py[n+1]=py[1];
	F(i,1,m) cin>>x[i]>>y[i]>>v[i];
	F(i,1,m){
		val[0][i]=v[i],dir[0][i]=1;
		val[10][i]=-INF;
		F(j,1,9){
			dir[j][i]=-1;
			switch((j-1)/3){
				case 0:{val[j][i]-=2*x[i];break;}
				case 2:{val[j][i]+=2*x[i];break;}
			}
			switch(j%3){
				case 1:{val[j][i]-=2*y[i];break;}
				case 0:{val[j][i]+=2*y[i];break;}
			}
		}
	}
	F(i,1,n){
		val[0][i+m]=-INF;
		val[10][i+m]=-abs(px[i]-px[i+1])-abs(py[i]-py[i+1]),dir[10][i+m]=-1;
		F(j,1,9){
			dir[j][i+m]=1;
			switch((j-1)/3){
				case 0:{val[j][i+m]+=px[i]+px[i+1];break;}
				case 1:{val[j][i+m]+=abs(px[i]-px[i+1]);break;}
				case 2:{val[j][i+m]+=-px[i]-px[i+1];break;}
			}
			switch(j%3){
				case 1:{val[j][i+m]+=py[i]+py[i+1];break;}
				case 2:{val[j][i+m]+=abs(py[i]-py[i+1]);break;}
				case 0:{val[j][i+m]+=-py[i]-py[i+1];break;}
			}
		}
	}
	F(i,1,m) F(j,1,9) q[0][j].emplace(val[0][i]+val[j][i],i);
	F(i,1,n) F(j,1,9) q[j][10].emplace(val[10][i+m]+val[j][i+m],i+m);
	F(i,1,n) ans+=abs(px[i]-px[i+1])+abs(py[i]-py[i+1]);
	F(k,1,n){
		F(i,0,10) F(j,0,10){
			while(!q[i][j].empty()&&!del[i][j].empty()&&q[i][j].top()==del[i][j].top()) q[i][j].pop(),del[i][j].pop();
			if(q[i][j].empty()) dis[i][j]=-INF;
			else dis[i][j]=q[i][j].top().fi;
		}
		memset(dep,-0x3f,sizeof(dep));
		static bool isin[11];
		queue<int>qu;
		qu.push(0);
		dep[0]=0,isin[0]=1;
		while(!qu.empty()){
			int now=qu.front();
			qu.pop();isin[now]=0;
			F(i,0,10) if(dep[i]<dep[now]+dis[now][i]){
				dep[i]=dep[now]+dis[now][i],fr[i]=now;
				if(!isin[i]) isin[i]=1,qu.push(i);
			}
		}
		ans+=dep[10];
		cout<<ans<<" ";
		int now=10,tp=0;
		static int u[11],v[11],mid[11];
		while(now){
			int i=fr[now],t=q[i][now].top().se;
			era(i,t,now);
			++tp,u[tp]=i,mid[tp]=t,v[tp]=now;
			now=i;
		}
		R(i,tp,1) dir[u[i]][mid[i]]*=-1,dir[v[i]][mid[i]]*=-1,val[u[i]][mid[i]]*=-1,val[v[i]][mid[i]]*=-1;
		while(tp) add(u[tp],mid[tp],v[tp]),--tp;
	}
	return 0;
}

题解：P12463 [Ynoi Easy Round 2018] 星野瑠美衣

文章操作

代码

相关推荐

评论

题解：P12463 [Ynoi Easy Round 2018] 星野瑠美衣