ABC273F Hammer 题解

题目大意

数轴上有 \(n\) 个锤子和 \(n\) 堵墙，第 \(i\) 个锤子位于 \(x_i\)，第 \(i\) 堵墙位于 \(y_i\)，第 \(i\) 个锤子可以对应的敲开第 \(i\) 堵墙。以原点为起点，给定终点 \(t\)，问最少移动多少个单位长度才能走到 \(t\)。必须拿到对应锤子敲开墙才能走过这堵墙。

Solve

考虑建图。对于一堵墙 \(y_i\)，对于所有必须先经过这堵墙才能到达的点 \(u\)，我们连一条从 \(y_i\) 到 \(u\) 的有向边，意为限制必须先经过 \(y_i\) 才能到 \(u\)。然后再连一条从 \(x_i\) 到 \(y_i\) 的有向边，意义同上。处理完之后再从原点向所有点连有向边。

先离散化，再在建出来的图上跑拓扑最长路即可，每条边的边权即为两端点位置之差。

至于为什么是最长路，由于图是在一个数轴上建出来的，比较特殊，所以一个点若受到多个点的约束，那么约束它的点之间一定也有约束关系，不会相互独立，所以更长的路一定包含更短的路的状态。意会一下。

无解的情况显然是从 \(s\) 到 \(t\) 的路径上有环，即约束 \(t\) 的条件无法全被满足，拓排完判断一下 \(t\) 的入度是否被消到 \(0\) 即可。

Code

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	short f=1;
	int x=0;
	char c=getchar();
	while(c<'0'||c>'9')	{if(c=='-')	f=-1;c=getchar();}
	while(c>='0'&&c<='9')	x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=1510,M=3010;
int n,s,t,x[N],y[N],k[M],ind[M],m;
long long f[M];
vector<int>e[M];
inline void topo()
{
	queue<int>q;q.push(s);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		if(u==t)    break;
		for(int i:e[u])
		{
			f[i]=max(f[i],f[u]+abs(k[i]-k[u]));
			if(!--ind[i])	q.push(i);
		}
	}
	if(ind[t])	puts("-1");
	else	printf("%lld",f[t]);
}
signed main()
{
	n=read();t=read();m=(n<<1);
	for(int i=1;i<=n;i=-~i)	k[i]=x[i]=read();
	for(int i=1;i<=n;i=-~i)	k[i+n]=y[i]=read();
	k[m+1]=0;k[m+2]=t;
	sort(k+1,k+m+3);
	m=unique(k+1,k+m+3)-k-1;
	for(int i=1;i<=n;i=-~i)
		x[i]=lower_bound(k+1,k+m+1,x[i])-k,
		y[i]=lower_bound(k+1,k+m+1,y[i])-k;
	t=lower_bound(k+1,k+m+1,t)-k;
	s=lower_bound(k+1,k+m+1,0)-k;
	for(int i=1;i<=n;i=-~i)
	{
		e[y[i]].push_back(x[i]);ind[x[i]]=-~ind[x[i]];
		if(x[i]>s)
			for(int j=x[i]+1;j<=m;j=-~j)
				e[x[i]].push_back(j),ind[j]=-~ind[j];
		else
			for(int j=1;j<x[i];j=-~j)
				e[x[i]].push_back(j),ind[j]=-~ind[j];
	}
	for(int i=1;i<=m;i=-~i)
		if(i!=s)	e[s].push_back(i),ind[i]=-~ind[i];
	return topo(),0;
}