最大权闭合子图

问题

给定一个有向图，点有点权（有正负），从中选出一个子图的点权和最大并且满足对于每一条有向边 \((u,v)\) ，若 \(u\) 在子图内则 \(v\) 必须在子图内部。

解法

考虑每一个点最后必然只存在于两种情况之中——在或不在最大权闭合子图中。因此我们考虑使用最小割，将位于最大权闭合子图中的点与 \(S\) 位于一个集合之中，否则与 \(T\) 在一个集合之中。

那么显然可以建边 \((S,u,val_u)\) ，表示割掉这条边我们就放弃这个点的权值。同时对于原图上的有向边，我们令其边权为 \(+\infty\) 。同时每一个点向汇点连去一条 \((u,T,0)\) 的边，表示分到和 \(S\) 一组不会损失权值。

但是考虑到权值可能存在负数，所以我们利用一个预流的 \(\text{trick}\) ，即先将 \(S\rightarrow u\rightarrow T\) 流 \(-val_u\) 的流量，同时将我们一开始的总权值减去对应的流量。转化之后我们相当于对负权点建 \((S,u,0)\) 和 \((u,T,-val_u)\) 两条边，答案就是所有正权点的和减去该图的最小割。

最大密度子图

问题

给定一张无向图，边有边权，点有点权，选出一个边集 \(\mathbb E\) ，令 \(\mathbb V\) 为边集中点对应的点集，最大化下式：

\[\text{res}=\frac{\sum_{e\in\mathbb E}val_e}{\sum_{u\in\mathbb V}val_u} \]

解法

考虑这个问题是一个很类似于 \(01\) 分数规划的东西，我们尝试用类似的解法来做，考虑二分这个答案 \(\text{mid}\) 。

\[\sum_{e\in\mathbb E}val_e\ge \text{mid}(\sum_{u\in\mathbb V}val_u)\\ \sum_{e\in\mathbb E}val_e-\text{mid}(\sum_{u\in\mathbb V}val_u)\ge 0\\ \]

所以我们要使得

\[\sum_{e\in\mathbb E}val_e-\text{mid}(\sum_{u\in\mathbb V}val_u) \]

最大。

算法一

考虑到我们前面的最大权闭合子图，发现我们这里需要满足边选择了，点就必须选。我们就给每一条边和点建出对应的点，并做最大权闭合子图即可。

算法二

诱导子图最小割。（不会）