已经改了标签
by kkksc03 @ 2016-07-20 21:12:41
算法思想概述
本题是一道最大权闭合子图模型，应用的算法为最大流(BFS增广即可)，定理为最大流最小割定理，辅助算法为拓扑排序。
问题初始建模
首先我们我建立图论模型，把每个植物当做一个顶点，植物携带的资源数目为顶点的权值。如果一个植物b在另一个植物a的攻击范围内，连接一条有向边<a,b>，表示a可以保护b。由于僵尸从右向左进攻，可以认为每个植物都被它右边相邻的植物保护，对于每个植物a（除最左边一列），向其左边的相邻植物b，连接一条有向边<a,b>。
由本题样例就可以发现，有一些植物是相互依赖的，于是我们可以进行算法实现的第一步：
1.使用拓扑排序去除图中的环，从而使图得到简化。
最大权闭合子图
进行算法的第二步。
2.对第一步中得到的图进行转置操作(把所有边反向)，从而得到最大子权闭合图。
样例的图经过拓扑排序和转置操作后如下：
其中最大权闭合子图为(1,2,4)
下面进行算法实现的第3、4步：
3.最大权闭合子图的网络流建模：
(1). 建立附加源S和附加汇T。
(2). 图中原有的转置后的边容量设为∞。
(3). 从S向每个权值为正的点连接一条容量为该点权值的有向边。
(4). 从每个权值不为正的点向T连接一条容量为该点权值绝对值的有向边。
建模后图如下：
4.求解：求S到T的最大流Maxflow，最大权闭合子图的权值就是(所有正权点权值之和 – Maxflow)，也就是需要输出的答案。
by Freddie @ 2019-07-08 19:38:58