lyoj 212 「雅礼集训 2017 Day8」价

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

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

他想知道，一次吃药最好情况下体重变化量是多少，当然可以一种药也不吃，此时体重不变。 由于某些奥妙重重的情况，我们可以让这 $N$种减肥药每一种对应一个其使用的药材，且$N$种减肥药对应的药材互不相同（即有完美匹配）。
##输入格式
第一行一个整数 $N$。

接下来$N$行，每行描述一种减肥药，对于一种减肥药，第一个数读入使用的药材个数 $t$，接下来 $t$个整数表示使用的药材编号，一个药材编号在一行只会出现一次。
最后一行 $N$ 个整数，第 $i$ 个整数 $P_i$ 表示第 $i$种减肥药产生效果时的体重变化量。
##输出格式
一行一个整数表示答案。
##样例
###样例输入
3
2 1 2
2 1 2
1 3
-10 20 -3
###样例输出
-3
##数据范围与提示
对于 $30\%$ 的数据， $N \leq 20$；
对于另外 $10\%$ 的数据， $P_i < 0$；
对于 $100\%$ 的数据， $1 \leq N \leq 300, |P_i| \leq 1000000$。

---
##题解

网络流

令药的集合为$S$,药材集合为$T$。

根据题意的要求可得：
###结论1:
若某方案药的集合为$S_1$,药材的集合为$T_1$。那么在整个最大匹配中，集合$S_1$中的元素一定是和集合$T_1$中的元素一一匹配的。

我们令最大匹配中与点$i$的匹配点为$Match_i$。
###结论2:
那么如果我们选择的点药$i$,而$i$含有药材$j$,那么我们一定也会同时选择药$Match_j$。

（感觉说的有点绕，自己感受一下就好了）
以下是对于上面那句话的证明

---

如果我们选择了$S_i$，与之匹配的是$T_i$而且$T_i$中存在元素$j$使得$Match_j$不再$S_i$中。
那么可得左边余下的元素比右边少一个，所以没法匹配，与结论1矛盾。

---

好了，现在就成了最大权闭合子图了。
如果减肥药效$P_i$为负，那么连接 $(S,i,-P_i)$。
如果为正，连接 $(Match_i,T,P_i)$。

求一个最小割即可。答案为 $(\sum{P_i < 0 ? -P_i:0}) - maxflow$

wuvin

导航

最近发表

友情链接