俭朴大白

文章
5
资源
0
加入时间
2年10月21天

poj 2135 有流量限制的最小费用最大流

题意:农场里有n块地,其中约翰的家在1号地,二n号地有个很大的仓库。农场有M条道路(双向),道路i连接着ai号地和bi号地,长度为ci。约翰希望按照从家里出发,经过若干块地后到达仓库,然后再返回家中的顺序带朋友参观。如果要求往返不能经过同一条路两次,求参观路线总长度的最小值。解析:如果只考虑去或者回的情况,问题只不过是无向图中两点之间的最短路问题。但是现在要去要