BZOJ 1877 [SDOI2009] 晨跑

发布于 2017-05-17  108 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1877

题意:一个 n 个点,m 条边的有向图,边有边权,每天的晨跑是一条从 1 到 n 的路径,每天的晨跑不能通过(除 1,n 外)重复的点,制定一个晨跑方案使得晨跑天数最多的同时满足总路程最小...


因为在练习费用流,所以知道它是费用流... 并不显然... 这道题大概是第一道真正意义上自己建模的 题了...

首先题目中有一个很严格的限制,点不能重复通过,我们这样处理它:将一个点 i 拆成\(x_i\) 和\(y_i\) 两个点,分别作为该点的出入点,连接该点的出入边,这样做提供了怎样的便利呢?就是我们可以方便的表示并存储“通过这个点”这个信息了,我们用一条边去沟通\(x_i\) 和\(y_i\),只要我们经过了这条边,就等价于通过了这个点,我们可以为这条边构造特殊的性质使得方便我们处理“一个点只能通过一次”这个约束。那么处理的方法就是显然的了,在\(x_i\) 和\(y_i\) 间连接一天流量为 1,费用为 0 的边,限制了流量自然只能跑一次。

对于题目中给出的边 (i,j),直接建立从 i 出点到 j 入点的一条流量 1 费用为路程的边即可。

当然,需要注意的是,由于点 1 和点 n 可以无限通过,我们需要为他们拆点时连流量为 inf,费用 0 的边。

本题很巧妙的转化思想就是将路程转移到费用上,用流量来限制“流过的次数”。当然,对于第一问,我们只需要记录增广次数即可啦!~

代码如下:

 


一个非常弱的准退役OIER