初学者对于上下界网络流的一些疑问

D_FANG @ 2025-01-10 22:26:29

by FLY_lai @ 2025-01-11 08:46:50

@D_FANG 可行流不一定等于最小流。得到上下界最小流要在 "超源向超汇最大流" 之后删去原汇到原源的无穷边，然后在残量网络上跑原汇到原源的最大流。

by D_FANG @ 2025-01-11 09:13:19

@FLY_lai 那么在支线剧情这道题里面，为什么又不用再跑一次原汇至原源的最小费用最大流呢？

by FLY_lai @ 2025-01-11 10:12:57

@D_FANG 如果是一般图求上下界最小费用可行流，需要在超源向超汇跑完最小费用可行流后，再跑原汇到原源的最大费用可行流。如果如你所说，在第一次跑完之后边权都是负数，那么第二次的最大费用可行流必然为 0，可以不用跑。

by FLY_lai @ 2025-01-11 10:16:05

一般图求最小费用可行流是第一次的费用减去第二次的费用

by FLY_lai @ 2025-01-11 10:49:04

噢不对！@D_FANG 我说错了，一般图应该先跑最小费用最大流而不是可行流。

by FLY_lai @ 2025-01-11 10:53:16

@D_FANG 等下，我说的好像全是错的，当我啥也没说，等我想一会

by D_FANG @ 2025-01-11 12:11:24

@FLY_lai 好的，orz

by FLY_lai @ 2025-01-11 12:21:28

@D_FANG

我想明白了。

首先有源汇可以 t\rightarrow s 的无穷边转化为无源汇。记 S 为超源，T 为超汇。

首先如果不是费用流：

• 可行流。S\rightarrow T 跑最大流检查 S 所有出边是否满流。
• 最大流。S\rightarrow T 跑最大流得到可行流，然后 s\rightarrow t 跑最大流，两次相加得到最大流。
• 最小流。S\rightarrow T 跑最大流得到可行流，然后 t\rightarrow s 跑最大流，第一次减第二次得到最小流。

然后对于费用流：

• 最大费用最大流。S\rightarrow T 最大费用最大流，之后 s\rightarrow t 跑最大费用最大流。
• 最小费用最大流。S\rightarrow T 最小费用最大流，之后 s\rightarrow t 跑最小费用最大流。
• 最大费用可行流。S\rightarrow T 最大费用最大流。这就已经可以了，因为得到了费用最大的可行流。当然，你也可以 s\rightarrow t 最大费用可行流相加，或者 t\rightarrow s 最小费用可行流作为减数。但是可能有正负环，如果无环第二次得到的一定是 0。
• 最小费用可行流。类似上面，S\rightarrow T 最小费用最大流即可。
• 最大费用最小流。先 S\rightarrow T 最大费用最大流得到最大费用的可行流，然后 t\rightarrow s 最小费用最大流。第一次减第二次。
• 最小费用最小流。先 S\rightarrow T 最小费用最大流，然后 t\rightarrow s 最大费用最大流。第一次减第二次。

支线剧情属于 "最小费用可行流"，只需要跑第一次就行了。

by D_FANG @ 2025-01-11 12:25:09

@FLY_lai thx,orz已关