本文主要是介绍poj 2135 有流量限制的最小费用最大流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
农场里有n块地，其中约翰的家在1号地，二n号地有个很大的仓库。
农场有M条道路（双向），道路i连接着ai号地和bi号地，长度为ci。
约翰希望按照从家里出发，经过若干块地后到达仓库，然后再返回家中的顺序带朋友参观。
如果要求往返不能经过同一条路两次，求参观路线总长度的最小值。
解析：
如果只考虑去或者回的情况，问题只不过是无向图中两点之间的最短路问题。
但是现在要去要回，并且不能经过相同的道路，这样。
如果先计算去时最短路，再计算回来时最短路，是不行的。（dp思想）
所以，来求从1号顶点到n号顶点的两条没有公共边的路径。
所以，把顶点之间连接一条流量为1，费用为路程的边。
这样转换之后，就是流量为2的最小费用流了。
敲了n遍有流量限制的网络流，终于a了。。。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cas这篇关于poj 2135 有流量限制的最小费用最大流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
