flag

「网络流 24 题」太空飞行计划

题解

看了 BYVoid 的题解 才明白.
设选中的实验集合为 $E_p$,仪器集合为 $I_p$,则需要最大化 $$\sum_{E_j\in E_p} p_j - \sum_{I_j\in I_p} c_j$$ 即最小化 $$\sum_{I_j\in I_p} c_j - \sum_{E_j\in E_p} p_j$$ 若将所有实验与仪器视作点,则可将选中的实验与仪器视作 s - t 割的 $S$ 集合,问题可转化为最小割.

构图

对于所有实验 $E_j$ 和仪器 $I_j$ 建点,并加入源点 $s$ 和汇点 $t$,需要加入的边有

  • 对于每个 $E_j$,连边 $(s, E_j, p_j)$
  • 对于每个 $E_j$,连边 $(E_j, I_k, +\infty)$,其中 $I_k \in R_j$
  • 对于每个 $I_j$,连边 $(I_j, t, c_j)$

设该网络的最小割 $C= (S, T)$,则选取所有 $S$ 中的实验和仪器时的净收入可表示为 $$w = \sum_{E_j\in E\cap S} p_j - \sum_{I_j\in I\cap S} c_j$$ 显然最小割 $C$ 的割集不包含容量为 $+\infty$ 的边,所以 $$cap(S, T) = \sum_{E_j\in E\setminus S} p_j + \sum_{I_j\in I\cap S} c_j$$ 从而有 $$w = \sum_{E_j\in E} p_j - cap(S, T)$$ 此时 $cap(S, T)$ 取得最小值,所以净收入 $w$ 有最大值.

输出方案

计算最大流(最小割容量)后,根据上式容易得到答案.
此题要求输出方案.Dinic 算法结束(残量网络中不存在 $s$ 到 $t$ 的路径)时,残量网络中从 $s$ 出发可达的所有点的集合是一个最小割的 $S$ 集合,所以只需输出 bfs 过程达到了的实验和仪器点的编号即可.

代码

这个跑得好慢.
24 题的输入格式都这么奇怪么..读换行没判断 \r WA 了几次..
loj6001_flow24.cpp