[CEOI2014] The Wall 题解

题意

\(~~~~\) 求在二维平面上选择一些有权值的线段并将给定的格子围住的最小权。

\(~~~~\) \(1\leq n,m\leq 400\) 。

题解

\(~~~~\) 神仙结论题目。

\(~~~~\) 首先这道题的结论是：将每个方格四周的点按照权值连边后，所有关键格子左上角的点到最左上角的最短路一定被围住或是边界的一部分。

\(~~~~\) 如何证明这个结论？考虑某个最优且某条最短路不被围住的方案：如图， \(v\) 为一关键格子，其中绿线为左上角到这个格子左上角的最短路，阴影部分为被圈住的区域。由于最短路的定义，则我们把选择红色线段的部分改为蓝色线段一定不会使花费更大，但与此同时被圈住的区域变大了，因此选择最短路一定是最优的。

\(~~~~\) 知道了这个结论我们可以怎么做呢？考虑把原先的点继续拆成左上、右上、右下、左下四个点，同时保留原先的边。当不在原图中的两个点不会跨过所有最短路时这两个点就可以连一条 \(0\) 权边。同时注意第一个点拆出的左上不能与其他点连接。最后我们再跑一次从第一个点的右上到第一个点的左下的最短路就可以得到答案了。

\(~~~~\) 比如下图就是样例一的转化后的图（每个点拆出来的点顺时针标号 \(0 \sim 3\)）

代码

#include <map>
#include <queue>
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
#define PII pair<ll,ll>
#define mp(a,b) make_pair(a,b)
using namespace std;
ll n,m;
ll L1[405][405],L2[405][405];
bool vil[405][405];
bool vis[2000005];
map<ll,bool>S[200000];
ll dis[1000005],fa[1000005];
vector < PII > G[1000005];
inline ll ID(ll x,ll y){return (x-1)*(m+1)+y;}
inline ll ID3(ll x,ll y,ll z){return ((x-1)*(m+1)+y-1)*4+z;}
struct cmp{
	bool operator()(const PII x,const PII y){return x.second>y.second;}
};
void Dij(ll N)
{
	priority_queue< PII,vector< PII >,cmp >Q;
	for(ll i=1;i<=N;i++) vis[i]=0,dis[i]=999999999999999999;
	Q.push(mp(1,0));dis[1]=0;
	while(!Q.empty())
	{
		ll u=Q.top().first;Q.pop();
		if(vis[u]) continue; vis[u]=true;
		for(ll i=0;i<G[u].size();i++)
		{
			ll v=G[u][i].first,w=G[u][i].second;
			if(!vis[v]&&dis[v]>dis[u]+w)
			{
				fa[v]=u;
				dis[v]=dis[u]+w;
				Q.push(mp(v,dis[v]));
			}
		}
	}
}
template<typename T>void print(T x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
void Tag(ll u)
{
	while(u!=1)
	{
//		prllf("ban:%d %d\n",fa[u],u);
		S[fa[u]][u]=S[u][fa[u]]=true;
		u=fa[u];
	}
}
void AddEdge(ll u,ll v,ll w){G[u].push_back(mp(v,w)); G[v].push_back(mp(u,w));assert(v>=0);/*prllf("%d %d %d\n",u,v,w);*/}
int main() {	
	scanf("%lld %lld",&n,&m);
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++) scanf("%d ",&vil[i][j]);
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1,x;j<=m+1;j++)
		{
			scanf("%lld",&x);L1[i][j]=x;
			ll u=ID(i,j),v=ID(i+1,j);
			G[u].push_back(mp(v,x));
			G[v].push_back(mp(u,x));
		}
	}
	for(ll i=1;i<=n+1;i++)
	{
		for(ll j=1,x;j<=m;j++)
		{
			scanf("%lld",&x);L2[i][j]=x;
			ll u=ID(i,j),v=ID(i,j+1);
			G[u].push_back(mp(v,x));
			G[v].push_back(mp(u,x));
		}
	}
	Dij((n+1)*(m+1));
	for(ll i=1;i<=n+1;i++)
		for(ll j=1;j<=m+1;j++) G[ID(i,j)].clear();
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++)
			if(vil[i][j]) Tag(ID(i,j));
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m+1;j++)
		{
			AddEdge(ID3(i,j,2),ID3(i+1,j,1),L1[i][j]);
			AddEdge(ID3(i,j,3),ID3(i+1,j,0),L1[i][j]);
			if(!S[ID(i,j)].count(ID(i+1,j)))
			{
				if(!vil[i][j-1]&&!vil[i][j]) AddEdge(ID3(i,j,2),ID3(i,j,3),0);
				if(!vil[i][j-1]&&!vil[i][j]&&(i!=1||j!=1)) AddEdge(ID3(i+1,j,0),ID3(i+1,j,1),0);
			}
		}
	}
	for(ll i=1;i<=n+1;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			AddEdge(ID3(i,j,1),ID3(i,j+1,0),L2[i][j]);
			AddEdge(ID3(i,j,2),ID3(i,j+1,3),L2[i][j]);
			if(!S[ID(i,j)].count(ID(i,j+1)))
			{
				if(!vil[i-1][j]&&!vil[i][j]) AddEdge(ID3(i,j,1),ID3(i,j,2),0);
				if(!vil[i-1][j]&&!vil[i][j]&&(i!=1||j!=1))AddEdge(ID3(i,j+1,0),ID3(i,j+1,3),0);	
			}
		}
	}
	for(ll i=1;i<=m+1;i++)
	{
		if(i!=1) AddEdge(ID3(1,i,1),ID3(1,i,0),0);
		AddEdge(ID3(n+1,i,2),ID3(n+1,i,3),0);
	}
	for(ll i=1;i<=n+1;i++)
	{
		if(i!=1) AddEdge(ID3(i,1,0),ID3(i,1,3),0);
		AddEdge(ID3(i,m+1,1),ID3(i,m+1,2),0);
	}
	Dij((n+1)*(m+1)*4);
	printf("%lld",dis[3]);
	return 0;
}