BZOJ 1927 [Sdoi2010] 星际竞速

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


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

题意:有 N 个星球,M 条航线,对于去某个星球 i 的方案,可以进行一次耗时\(a_i\) 的跳跃,或者通过某条以 i 点为终点的单向边,需要注意的是,给出的边是双向的,然而只有从编号较小到较大的路径才合法... 求最小耗时


显然是一个费用流,我们采取如下的拆点策略:

对于点 i,我们拆成入点 i 和出点 i',对于合法边 (i,j),连一条 i 到 j'的边,容量 1,费用边长。

然后我们考虑跳跃,添加源汇后分别从源汇向 i 点,i'点连接容量 1,费用 0 的边,跳跃就可以通过连 S 到 i'的边处理...

说起来比较抽象,详见代码... 特意把 M 开大,结果因为 N 开小狂 TLE 狂 RE.... 调了快 3h

 


一个非常弱的准退役OIER