我个人觉得：

这类题，要的不是整体的最小费用，一般都是二分答案（最长所允许添加的边的费用），筛掉二分时mid之上费用的边，然后用最大流算看它是不是满流的来决定继续怎么分。

至于那个正反边都建的问题，其实它是不可能正反都走的，因为我们的目的是要让路径走的最长的那条尽可能短。如果都走的话，看下面的图
    A
   /\
  /  \
 B----C
 \   /
  \ /
   D
假设我们先走A->B->C->D,再走A->C->B->D。那么实际上，我可以直接走A->B->D和A->C->D。B->C这一段是完全剩下的。也就是说，对于任何一条被走正反两次的路，你正走的那个起点和反走的那个终点其实是同一个点，先前走的那条路的前一半A->B,必然和之后走的路的后一半B->D相连，对于另一边也是这样。完全可以不走那段被重复走的。而且如果走了中间那段，反而是多走的。

至于用单源最短路先定下边的方向，无法保证正确，仔细想想就很容易举出反例了。

• Re:涛哥，不知道你还会不会看见这个回复 (17) cxjyxx_me 2012-03-02 19:44:31