ShinriiTin/notes/network_flow
网络流学习笔记
上下界网络流
1.无源无汇有容量下界网络的可行流
\(step1.\) 建立附加源 \(s\) 和汇 \(t\)。
\(step2.\) 添加弧 \(t\to s\) 并设容量为无穷大。
\(step3.\) 将原图中上界为 \(c\)，下界为 \(b\) 的弧 \(u\to v\) 拆成三条弧：\(s\to v\) 和 \(u \to t\)，容量都为 \(b\)，以及 \(u\to v\)，流量为 \(c-b\)。
\(step4.\) 对附加弧进行合并：对于原图中每个点 \(i\) 记录 \(d[i]=\sum\limits_{e:s\to i} cap(e) - \sum\limits_{e:i\to t} cap(e)\)。 如果 \(d[i]>0\)，则连一条容量为 \(d[i]\) 的弧 \(s\to i\)；如果 \(d[i]<0\)，则连一条容量为 \(-d[i]\) 的弧 \(i\to t\)。
\(step5.\) 求改造后的网络的s-t最大流，当且仅当所有的附加弧满载时原网络有可行流。
例题
2.有源汇有容量下界网络的s-t可行流
\(step1.\) 建立超级源 \(ss\) 和 \(tt\)。
\(step2.\) 添加弧 \(t\to s\) 并设容量为无穷大。
\(step3.\) 将原图中上界为 \(c\)，下界为 \(b\) 的弧 \(u\to v\) 拆成三条弧：\(ss\to v\) 和 \(u \to tt\)，容量都为 \(b\)，以及 \(u\to v\)，流量为 \(c-b\)。
\(step4.\) 对附加弧进行合并：对于原图中每个点 \(i\) 记录 \(d[i]=\sum\limits_{e:ss\to i} cap(e) - \sum\limits_{e:i\to tt} cap(e)\)。 如果 \(d[i]>0\)，则连一条容量为 \(d[i]\) 的弧 \(ss\to i\)，如果 \(d[i]<0\)，则连一条容量为 \(-d[i]\) 的弧 \(i\to tt\)。
\(step5.\) 求改造后的网络的ss-tt最大流，当且仅当所有的附加弧满载时原网络有s-t可行流。
