【JZOJ4893】过河 题解

题目大意

  有条河，河的一岸是直线 y=0，另一岸是直线 y=w，长度无限。
  河上有 n 个木桩，坐标为 (x[i],y[i])，每个木桩上可以搭一个圆盘。共有 m 种圆盘，每种半径为 r[i]，价格为 c[i]。圆盘可以伸到岸上。
  两个圆盘连通当且仅当相切或相交。
  问如何搭圆盘，能以最小的价格从河的一岸走到另一岸。若走不到则-1。
  数据组数<=10；n,m<=250；w,x,r<=10^9；y<=w；c<=10^6

样例

  类似这样

【60%】n,m<=35

  拆点。每个木桩搭配每种盘子都作为一个点，则一共有 n×m 个点。
  再暴力把边连上，跑最短路。

【另25%】所有x=0

  相当于所有点在一条轴上，那就搞个dp。
  设 f[i][j] 表示第 i 个桩，放第 j 种盘，的最小代价。转移时加些前缀优化就可以做到3次方。

【100%】n,m<=250

  考虑60分的那个最短路模型，关键就是要把边的数量压下来。
  首先，如果有盘子半径比别人小，价格又比别人贵，肯定是没用的。用排序加单调栈去掉这些盘子，这样盘子就单调了。
  一个点表示为 (a,b)，表示第 a 个桩放第 b 种圆盘。
  我们观察可得，连边最浪费的就是，假设 (a,b) 要连向 (c,d)，那所有可能的 d 都要连一次。想想，我们如果连向第 d 种盘子，那就已经代表了比它大的盘子都可以连，这就可以去掉一些冗边。
  所以对于 (a,b) 连向第 c 个桩，我们只连半径最小的 d。然后对于每个点 (a,b)，向 (a,b+1) 连一条长度为 c[b+1]-c[b] 的边（当然这里的盘子是排好序的）。这样就实现了上述想法，并且把边数压到了 n^2m。

代码

  //其实边数还是很大，这种图应当要用Dijkstra，但是我写了spfa。

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

typedef long long LL;

const int maxn=255, maxp=63000, maxe=18e6+5;
const double sml=1e-7;

struct P{
	int r,c;
};
bool cmp(const P &a,const P &b) {return a.r<b.r || a.r==b.r && a.c>b.c;}

int n,m,w,sum,x[maxn],y[maxn];
P p1[maxn],p[maxn];

int tot,go[maxe],val[maxe],next[maxe],f1[maxp];
void ins(int x,int y,int z)
{
	go[++tot]=y;
	val[tot]=z;
	next[tot]=f1[x];
	f1[x]=tot;
}

double DIS(int a,int b)
{
	return sqrt((double)(x[a]-x[b])*(x[a]-x[b])+(double)(y[a]-y[b])*(y[a]-y[b]));
}

LL dis[maxp],inf;
int d[8*maxp];
bool bz[maxp];
void spfa()
{
	memset(dis,127,sizeof(dis)); dis[0]=0;
	inf=dis[1];
	bz[0]=1;
	d[1]=0;
	int maxi=7*maxp;
	for(int i=1, j=1, ii=1, jj=1; ii<=jj; ii++, i=i%maxi+1)
	{
		for(int p=f1[d[i]]; p; p=next[p]) if (dis[go[p]]>dis[d[i]]+val[p])
		{
			dis[go[p]]=dis[d[i]]+val[p];
			if (!bz[go[p]])
			{
				jj++;
				j=j%maxi+1;
				bz[ d[j]=go[p] ]=1;
				if (dis[d[i%maxi+1]]>dis[d[j]]) swap(d[i%maxi+1],d[j]);
			}
		}
		bz[d[i]]=0;
	}
}

int T;
int main()
{
	scanf("%d",&T);
	while (T--)
	{
		scanf("%d %d %d",&n,&m,&w);
		sum=n*m+1;
		fo(i,1,n) scanf("%d %d",&x[i],&y[i]);
		fo(i,1,m) scanf("%d %d",&p1[i].r,&p1[i].c);
		sort(p1+1,p1+1+m,cmp);
		int m0=0;
		fo(i,1,m)
		{
			p[++m0]=p1[i];
			while (m0>1 && p[m0-1].r<=p[m0].r && p[m0-1].c>=p[m0].c)
			{
				m0--;
				p[m0]=p[m0+1];
			}
		}
		m=m0;
		
		tot=0;
		memset(f1,0,sizeof(f1));
		fo(i,1,n)
			fo(j,1,n) if (i!=j)
			{
				double ds=DIS(i,j)-sml;
				int jm=m+1;
				fo(im,1,m)
				{
					while (jm>1 && ds<=(LL)p[im].r+p[jm-1].r) jm--;
					if (jm && jm<=m) ins((i-1)*m+im,(j-1)*m+jm,p[jm].c);
				}
			}
		fo(i,1,n)
			fo(im,1,m)
			{
				if (p[im].r>=y[i]) ins(0,(i-1)*m+im,p[im].c);
				if (p[im].r>=w-y[i]) ins((i-1)*m+im,sum,0);
				if (im<m) ins((i-1)*m+im,(i-1)*m+im+1,p[im+1].c-p[im].c);
			}
		
		spfa();
		
		if (dis[sum]==inf) printf("impossible\n"); else printf("%lld\n",dis[sum]);
	}
}