HDU 2013 杭州网络赛 1007 & HDU 4744 Starloop System - Wall_F的专栏 - 博客频道 - CSDN.NET

文章价值(3) ?
阅读数(157) ?

网赛开始10分钟后开始读这题,然后立马发现这是求循环流,这一题的做法是拆点后求在满足最大流的情况下的最小费用。。

即要使得第i个每个城市属于wi个循环圈,把每个点拆成两个点,建立超级源点s,汇点t,对每个城市i来说s->i连wi的流量,费用为0的边。

i+n->t,连wi的流量,费用为0的边。?

城市与城市之间,i>j+n 连流量为INF,费用为cost的边。跑最小费用最大流即可。

最后判断最终的流量是否等于所有的wi之和。


PS:然后过测试数据,全过。然后看看board,发现没人交兴奋了一把,然后立马跟队友说了一声我交了,结果交上去TLE。。。

看看数据量n<=100,应该不会超时的啊。

然后改MCMF算法。。 然后各种TLE。

由于没有负圈,最后改为ZKW_flow在稠密图上跑,交上去还是TLE。。。?

因为浪费太多时间了,一个人最后也想不到优化了,只好作罢。。

由于以前一般题的SPFA找增广路是可以满足条件的,所以从来没写过ZKW_flow。。。赛后看看其他队伍AC提交的情况。由于从来没写过ZKW_flow,发现ZKW_flow写龊了。。而且他们是800+MS,900+MS卡着时间过的。

诶,只能怪运气不好吧。


渣代码略。。。。

版权声明:本文为博主原创文章,未经博主允许不得转载。





(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: