如果要你求一个网络中只有一条路径的最大流，应该用什么算法。（原题：http://online-judge.uva.es/p/v5/544.html）

首先，我们通常用的最大流算法Ford-Fulkerson算法是不能用了。

然而，我们可以用最短路径的算法，Dijkstra或Floyd-Warshall加以修改，来解决这个问题。因为这个问题实际就是要找出一条容量最大的路径。

但是我们同时也知道另一件事，很多人初学的时候都会通过把Dijkstra和Floyd-Warshall里的小于号改成大于号来求最长路径。结果显然是错误的，因为这样的算法算出的最长路径中会有重复的边。为什么，很简单，Dijkstra和Floyd-Warshall里都无法限制重复边的出现，但是在最短路径中，如果一条路径有重复的边，那它肯定不会是最短路径，所以重复边被问题本身的性质剃除了。但是如果用来求最长路径，那么越有重复的边，路径就越长，就越满足要求，则最终的结果就会错误了。

所以如果要看一个问题能不能用Dijkstra和Floyd-Warshall来解决，只要看有重复边的路径是否会比没有重复边有路径更符合问题的要求。比如求容量最大的路径时，重复的边不可能使容量变大，因为容量取决于路径中容量最小的一条边。

还有一个同类的问题：用2种颜色可不可能给一张地图着色，使每两个相邻的国家颜色都不同。解法是看一个无向图中存不存在边数为奇数的圈。同样，在这个问题里，有重复边有路径不可能改变原有的解，所以可以用Dijkstra或Floyd-Warshall来解。