P6545 [CEOI2014] The Wall 做题记录

P6545 [CEOI2014] The Wall

首先有个结论,筑的墙一定会把 (1,1)(1,1) 到所有别的关键点的左上角的最短路都围进去。例如:

若当前墙包含的是深蓝色区域,而 (1,1)(1,1) 到关键点 uu 的左上角的最短路是绿色的线,那么显然把浅蓝色区域也包含进墙里是更优的,因为红色段肯定是比代替它的五小段绿色段的长度和要长的,因为绿色的线是最短路。

为什么是左上角?其实四个角都没关系,这个之后再证明。

求出了 (1,1)(1,1) 到别的关键点的左上角的最短路之后,问题就转化为最小化筑墙的花费,使得筑出的墙可以圈住所有的最短路和关键点。

那么考虑把一个网格线的交点都拆成四个点,点之间顺时针连边权为 00 的有向边,属于不同交点的点之间连边权为原权值的有向边,但是要注意经过关键点和最短路的边都不能连

容易发现,这样建好图之后,从网格左上角的交点拆出来的 11 号点出发,走到它的 33 号点,就能筑出合法的墙。那么花费最小的方案显然就是这两点之间的最短路。

最后说一下之前留下来的悬念:

为什么要走到左上角???为什么走到哪个角都没关系???

不妨先钦定一定从左上角那个关键点的左上角出发,显然走到右上角的最短路一定“围着”走到左上角的最短路,即绿色的线不可能越过红色的线再回来,因为那样不优。

那么分两种情况讨论:

  • 走到左上角的最短路先走到右上角再往左走:

    这时由于最后筑的墙要包含所有关键点,所以左上角和右上角之间的那条边不会被筑墙,也就是说,红线和绿线有用的部分是完全相等的,那么自然对答案没有任何影响;

  • 走到左上角的最短路不是先走到右上角再往左走:

    这时考虑最后跑的最短路,即筑的墙,用紫色的线标识。显然,由于走到左上角的最短路不是先走到右上角再往左走,所以走左上角和右上角的那条边一定是不优的;并且走红线和绿线中间也是不优的,因为红线和绿线是最短路。那么最终的墙只有可能是这样:

    所以对最终的答案没有影响;

参考这样的证明方法,容易得出从哪个角出发,走到哪个角都是没有任何关系的。所以为了好写,干脆直接钦定从左上角开始和结束。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int S=5000005,MS=405;

int n,m;
int a[MS][MS];
long long dnval[MS][MS],rgval[MS][MS];
int esum,to[S],nxt[S],h[S];
long long c[S],dis[S];
bool vis[S];
bool dntag[MS][MS],rgtag[MS][MS];

inline int getid(int x,int y)
{
	return (x-1)*(m+1)+y;
}

inline int getx(int id)
{
	return (id-1)/(m+1)+1;
}

inline int gety(int id)
{
	return (id-1)%(m+1)+1;
}

inline void add(int x,int y,long long w)
{
	to[++esum]=y;
	c[esum]=w;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline void dijkstra(int s)
{
	memset(dis,127,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	priority_queue<pair<long long,int> > q;
	q.push(make_pair(-dis[s],s));
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=true;
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i];
			long long w=c[i];
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
}

void dfs(int u)
{
	vis[u]=true;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		long long w=c[i];
		if(dis[u]==dis[v]+w)
		{
			int ux=getx(u),uy=gety(u),vx=getx(v),vy=gety(v);
			if(vx!=ux) dntag[min(ux,vx)][uy]=true;
			else rgtag[ux][min(uy,vy)]=true;
			if(!vis[v]) dfs(v);
			break;
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m+1;j++)
		{
			scanf("%lld",&dnval[i][j]);
			int idu=getid(i,j),idv=getid(i+1,j);
			add(idu,idv,dnval[i][j]);
			add(idv,idu,dnval[i][j]);
		}
	}
	for(int i=1;i<=n+1;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%lld",&rgval[i][j]);
			int idu=getid(i,j),idv=getid(i,j+1);
			add(idu,idv,rgval[i][j]);
			add(idv,idu,rgval[i][j]);
		}
	}
	dijkstra(getid(1,1));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]==1&&!vis[getid(i,j)]) dfs(getid(i,j));
	esum=0;
	memset(h,0,sizeof(h));
	for(int i=1;i<=n+1;i++)
	{
		for(int j=1;j<=m+1;j++)
		{
			int bg=(getid(i,j)-1)*4;
			int _0=bg+1,_1=bg+2,_2=bg+3,_3=bg+4;
			if(!dntag[i-1][j]&&a[i-1][j-1]==0&&a[i-1][j]==0) add(_0,_1,0);
			if(!rgtag[i][j]&&a[i-1][j]==0&&a[i][j]==0) add(_1,_2,0);
			if(!dntag[i][j]&&a[i][j]==0&&a[i][j-1]==0) add(_2,_3,0);
			if(!rgtag[i][j-1]&&a[i][j-1]==0&&a[i-1][j-1]==0) add(_3,_0,0);
			if(i>1)
			{
				int ubg=(getid(i-1,j)-1)*4;
				int u2=ubg+3,u3=ubg+4;
				add(u2,_1,dnval[i-1][j]);
				add(_0,u3,dnval[i-1][j]);
			}
			if(j>1)
			{
				int lbg=(getid(i,j-1)-1)*4;
				int l1=lbg+2,l2=lbg+3;
				add(l1,_0,rgval[i][j-1]);
				add(_3,l2,rgval[i][j-1]);
			}
		}
	}
	dijkstra(2);
	printf("%lld\n",dis[4]);
	return 0;
}