wuvin

题目描述

人类智慧之神 zhangzj 最近有点胖，所以要减肥，他买了 $N$ 种减肥药，发现每种减肥药使用了若干种药材，总共正好有 $N$ 种不同的药材。

经过他的人脑实验，他发现如果他吃下去了 $K （ 0 \leq K \leq N )$种减肥药，而这 $K$ 种减肥药使用的药材并集大小也为 $K$ ，这 $K$ 种才会有效果，否则无效。
第 $i$ 种减肥药在产生效果的时候会使 zhangzj 的体重增加 $P_i$斤，显然 $P_i$ 可以小于 $0$。

他想知道，一次吃药最好情况下体重变化量是多少，当然可以一种药也不吃，此时体重不变。 由于某些奥妙重重的情况，我们可以让这 $N$种减肥药每一种对应一个其使用的药材，且

1、要清楚，最好纸上画出来。

2、要优化：根据网络流建模汇总里说的

• 如果几个结点的流量的来源完全相同，则可以把它们合并成一个。

• 如果几个结点的流量的去向完全相同，则可以把它们合并成一个。

• 如果从点 u 到点 v 有一条容量为∞的边，并且点 v 除了点 u 以外没有别的流量来源，则可以把这两个结点合并成一个。

• 如果点u只有一个来源和一个去向，则可以保留容量最小边，删除点u.

3、对于边的构建的优化

4、如果确定图形可以是平面图，考虑对偶图。