C/C++教程

「POJ2175」Evacuation Plan

本文主要是介绍「POJ2175」Evacuation Plan，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

点这里看题目。

分析

显而易见的方法：直接建图跑一个最小费用最大流，然后比较自己得到的结果和给出的方案。

但是这里有 \(O(n^2)\) 条边，再加上流量可以被构造得很大，因此这种方法不出所料地超时了。

注意到，题目给出的方案一定是一个最大流的方案，但不一定是最小费用的方案。换句话说，题目其实给出了一个残量网络。根据完全不众所周知的消圈原理，如果这个残量网络上存在负环，那么这个流就一定不是最小费用流。另外，如果搜索到了一个负环，我们也可以在这个负环上调整 1 的流量，从而得到一种更优的方案，因此也可以很容易地构造出方案。

理论的复杂度应为 \(O(n^2m)\)，勉强能够过去。如果使用 DFS 版本的 SPFA 并加上若干优化，那么就能跑得飞快

这篇关于「POJ2175」Evacuation Plan的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航