标签 - 网络流

? solution ? ? 网络流 ?    2017-03-22 21:11:15    592    0    0

题目描述

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

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

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

? 知识点 ? ? 网络流 ?    2017-03-19 19:16:23    354    0    0

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

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

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

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

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

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

3、对于边的构建的优化

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