P6545【CEOI2014 Wall】题解

· · 题解

一、定义

我们的任务即是要确定一种合法的筑墙方案（其区域包含了所有关键方格的四个角），使得筑墙的代价最小

二、引理

我们用归纳调整的思想。假设我们已经求出一个合法的筑墙方案，且存在一个关键方格 u，满足左上角到此点左上角的最短路不被包含在区域内。显然地，此最短路一定被这道墙分割成了若干段，在墙内的段和在墙外的段交替出现。我们把区域扩展到在墙外的段（即用这部分在墙外的段代替连接这一段两端点的墙的部分），相当于把原墙和最短路部分合并。这样，不仅墙的区域扩大了，而且由最短路的定义，新方案的代价肯定不劣于原方案。于是新的方案肯定不劣。一直这样调整下去直到无法继续进行优化，最终得到的结果便满足原命题的任意一个状态。

引理即得证。

三、做法

现在我们的任务就是，给定一些最短路，求出包含这些最短路（即墙的区域包含所有最短路上的点）的方案的最小代价。

又因为所有最短路构成了一棵最短路树，所以我们只要满足筑墙方案不穿过最短路即可。考虑把每一个点再拆成四个小点（一个方格对应 16 个点），在原图基础上再在相邻的、不穿过任意一条最短路树的边两点之间连一条边权为 0 的边，跑最短路即可。

四、代码

实在太难实现了，先鸽子了.jpg（