BZOJ1565 植物大战僵尸

题解

题目链接

我觉得这题是个不错的网络流题目,应用到了对最大权闭合图的理解。

引用一位dalao对闭合图的解释:

闭合图:定义一个有向图 $G = (V , E)$ 的闭合图,是该有向图的一个点集,且该点集的所有出边都还指向该点 集。即闭合图内的任意点的任意后继也一定在闭合图中。更形式化地说,闭合图是这样的一个点集 $V ‘ \in V$ ,满足对于 $\forall u\in V’$ 引出的 ,必有 $v \in V ‘$ 成立。按照上面的定义,闭合图是允许超过一个连通块的。
在许多实际应用中,给出的有向图常常是一个有向无环图( $DAG$ ),闭合图的性质恰好反映了事件间的必要条件的关系:一个事件的发生,它所需要的所有前提也都要发生。一个常见的例子就是制定大学的选课计划,其中一些课程需要以另一些课程为基础,这就是给出了有向无环图。若给所有课程打分,最大权闭合图对应了获益最大或效率最高的选课计划,解决了这个问题,就可以容易地选出一个最合理的选课计划。
继续阅读