最大权闭合图

昨天在做多校联赛的时候偶然碰上的,学习了下这个,首先推荐胡伯涛的《最小割模型在信息学竞赛中的应用》。
一个有向图 的闭合图(closure)$$G= (V , E)$$是该有向图的一个点集,且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。更形式化地说,闭合图是这样的一个点集$${V}’\in {V}$$ ,满足对于 $$\forall {u}\in {V}$$引出的 $$\forall \left \langle u,v \right \rangle \in E$$。那么给每个点$$v$$分配一个点权$$W_{v}$$(任意实数,可正可负)。大权闭合图(maximum weight closure),是一个点权之和大的闭合图,即大化$$\sum_{ v\in {V}’ }W_{v}$$。

那么,我们的做法就是当$$W_{v}$$是负的时候,建一条边$$\left \langle v,t \right \rangle$$容量为$$-W_{v}$$,当$$W_{v}$$是正的时候,建一条边$$\left \langle s,v \right \rangle$$容量为$$W_{v}$$,然后对于原来的边$$\left \langle {u}’,{v}’ \right \rangle$$保持不变,建一条$$\left \langle {u}’,{v}’ \right \rangle$$容量为$${inf}$$的边。那么易证这个图的在最小割的情况下,和$${s}$$相联通的子图是最大权闭合子图。
所以我们做法就是跑一次最大流,然后最大权闭合图的权值就是总收益-最大流。

POJ2987
这是一个非常裸地最大权闭合图,当$$W_{v}$$是负的时候,建一条边$$\left \langle v,t \right \rangle$$容量为$$-W_{v}$$,当$$W_{v}$$是正的时候,建一条边$$\left \langle s,v \right \rangle$$容量为$$W_{v}$$,然后对于原来的边$$\left \langle {u}’,{v}’ \right \rangle$$保持不变,建一条$$\left \langle {u}’,{v}’ \right \rangle$$容量为$${inf}$$的边。
然后直接按照原理跑一下最大流就好。

HDU4971

水题。

HDU5855
首先膜拜一下朝鲜队的出题大哥,题目质量太好了。
这道题我们直接二分最短的时间,然后对于每一次时间判断一下最大权闭合图是不是大于L就好。

 

POJ_1815_Friendship

这个题建图需要有一些技巧,先说题意:给定一个无向图和问假如使其中的某两个点不连通,至少需要删除几个点。

建图:

1.原图中每个顶点v变为两个点v1和v2,顶点v1到v2建一条容量为1的边。

2.对于原来的每一条边e=(u,v),变成两条弧u2-v1和v2-u1。

3.令s1为源点t2为汇点。

然后就直接跑一下网络流最大流。