一般的方法大家都知道，把无向边拆成有向边，超级源点向源点加一条流量为2，费用为0，超级汇点类似。
但是有个问题需要注意，如何保证拆边之后的路径一定是最优的呢？
比如说如下图：
a-b
a-c
b-c
c-d
可不可以走a->b->a->c->d呢？当然可以，但是由于拆边之后没有负费用，我们肯定能找到一条更优的路径。比如说a->c->d。由于是最小费用，所以通过这样的方法就保证了不会走同一条路两次。
而从源点到汇点的最大流则表示了共有多少不重复的路径。
一般的方法大家都知道，把无向边拆成有向边，超级源点向源点加一条流量为2，费用为0，超级汇点类似。
但是有个问题需要注意，如何保证拆边之后的路径一定是最优的呢？
比如说如下图：
a-b
a-c
b-c
c-d
可不可以走a->b->a->c->d呢？当然可以，但是由于拆边之后没有负费用，我们肯定能找到一条更优的路径。比如说a->c->d。由于是最小费用，所以通过这样的方法就保证了不会走同一条路两次。
而从源点到汇点的最大流则表示了共有多少不重复的路径。