Sum of Abs

题目大意

$N$ 个点 $M$ 条边的无向图，每个点有两个权值 $A_i$ 和 $B_i$。可以用 $A_i$ 的代价删除第 $i$ 个节点。并删除与这个点相连的边。

一个极大连通块的权值定义为 $B_i$ 的权值和的绝对值。 删除一些节点后，收益定义为所有极大连通块权值之和减去代价和，求最大的可能收益。

思路

对于这种不是被割掉就是产生贡献的题目，考虑使用网络流。

将点 $i$ 拆成 $i'$ 和 $i''$ 分别表示没有被删除的点 $i$ 造成了 $b_i$ 或者 $-b_i$ 的贡献。

将 $S$ 与 $i'$ 连一条流量为 $a_i-b_i$ 的边 ，如果这条边被割了就代表这个连通块内的取的是 $b_i$；反之，如果 $i''$ 与 $S$ 连的流量为 $a_i+b_i$ 的边被割了，那么就代表这个连通块内取的是 $-b_i$ 。特别的，如果 $S$ 与 $i'$ 和 $i''$ 与 $T$ 的边都被割了，那么就代表 $i$ 被删除了。

显然一个点 $i$ 不可能在同时造成 $b_i$ 和 $-b_i$ 的贡献，所以我们将 $i'$ 和 $i''$ 之间连一条流量为 $inf$ 的边，这样就保证 $i'$ 和 $i''$ 之间肯定有一个点和 $S$ 或 $T$ 的连边被割断。

对于一条边 $x,y$，考虑连两条权值为 $inf$ 的 $x’\to y''$ 和 $y'\to x''$，这样就保证了 $b_x$ 与 $b_y$ 在取值是必须同时乘 $-1$ 或者保持原样。

所以最终的答案就是 $\sum\limits_{i=1}^{n}a_i-\operatorname{MaxFlow}$，时间复杂度为 $O(n^3)$。

Submission #55848640 - AtCoder Regular Contest 107