警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「NOI 2008」志愿者招募 - 费用流

此题写于 2019-02-10 17:17:54

题意

传送门:洛谷 P3980 - 志愿者招募

解法

定义 \(x\xrightarrow{a,b}y\) 为:从 \(x\)\(y\) 连一条流量为 \(a\)、费用为 \(b\) 的边。

首先考虑志愿者人数作为流量,代价作为费用。

开一个超级源 \(S\) 和一个超级汇 \(T\)。连两条边 \(S\xrightarrow{f,0}1,(n+1)\xrightarrow{f,0}T\),其中 \(f\) 是一个充分大的数,在程序可以直接取 \(+\infty\)

那么 \(i\) 号点到 \(i+1\) 号点应该连一条 \(f-a_i\) 的边。

算法为了保证最大流为 \(f\),会尝试寻找其它的边增广。

于是对于第 \(i\) 类志愿者,在图中连一条 \(s_i\xrightarrow{+\infty,c_i}(t_i+1)\)

显而易见,这张图的最小费用就是答案。

一句话建模:\(S\xrightarrow{f,0}1,\forall_{i\in[1,n]}i\xrightarrow{f,0}(i+1),(n+1)\xrightarrow{f,0}T,\forall_{i\in m}s_i\xrightarrow{+\infty,c_i}(t_i+1),ans=\operatorname{mincost}(S\to T)\)

代码