给定N颗星球，M条航道，每颗星球都有一个引力值。你驾驶着一艘飞船，这艘飞船有两种模式，一种是高速行驶模式，另一种是能力爆发模式。高速行驶模式下，只能由一个星球前往引力比他大的星球，并且要花费这条航道权值的时间。能力爆发模式下，可以从一个星球到达任意一个星球，需要花费所到达星球的定位时间。比赛要求从一个和这N个星球没有任何航路的星球出发，然后遍历所有的N个节点恰好一次。现在你要设计一种方案，求出花费时间的最小值。
1<=N<=800, 0<=M<=15000
显然到一个点的方式有两种。花费时间的最小值与小数据就可以知道这题是费用流。
想想费用是什么吧。一种直接到这个点花定位时间，一种从一个点到另一个点。（一个点只能到一个点）
于是考虑拆点，S向每个点的x连f=1，w=0的边，每个点的y向T连f=1，w=0的边。这时候最大流就能保证每个点都被跑过。
S向每个点的y连f=1，w为定位时间的边。把航道在xy中连起来，f=1，w为航道权值的时间。（因为每条边的流为1，所以保证一个点出发只会到一个点）
费用流即可。
原文：http://www.cnblogs.com/Dndlns/p/7979350.html