上下界網絡流

在閲讀這篇文章之前請先閲讀最大流並確保自己熟練掌握最大流算法。

概述

上下界網絡流本質是給流量網絡的每一條邊設置了流量上界 \(c(u,v)\) 和流量下界 \(b(u,v)\)。也就是説，一種可行的流必須滿足 \(b(u,v) \leq f(u,v) \leq c(u,v)\)。同時必須滿足除了源點和匯點之外的其餘點流量平衡。

根據題目要求，我們可以使用上下界網絡流解決不同問題。

給定無源匯流量網絡 \(G\)。詢問是否存在一種標定每條邊流量的方式，使得每條邊流量滿足上下界同時每一個點流量平衡。

不妨假設每條邊已經流了 \(b(u,v)\) 的流量，設其為初始流。同時我們在新圖中加入 \(u\) 連向 \(v\) 的流量為 \(c(u,v) - b(u,v)\) 的邊。考慮在新圖上進行調整。

由於最大流需要滿足初始流量平衡條件（最大流可以看成是下界為 \(0\) 的上下界最大流），但是構造出來的初始流很有可能不滿足初始流量平衡。假設一個點初始流入流量減初始流出流量為 \(M\)。

若 \(M=0\)，此時流量平衡，不需要附加邊。

若 \(M>0\)，此時入流量過大，需要新建附加源點 \(S'\)，\(S'\) 向其連流量為 \(M\) 的附加邊。

若 \(M<0\)，此時出流量過大，需要新建附加匯點 \(T'\)，其向 \(T'\) 連流量為 \(-M\) 的附加邊。

如果附加邊滿流，説明這一個點的流量平衡條件可以滿足，否則這個點的流量平衡條件不滿足。（因為原圖加上附加流之後才會滿足原圖中的流量平衡。）

在建圖完畢之後跑 \(S'\) 到 \(T'\) 的最大流，若 \(S'\) 連出去的邊全部滿流，則存在可行流，否則不存在。

給定有源匯流量網絡 \(G\)。詢問是否存在一種標定每條邊流量的方式，使得每條邊流量滿足上下界同時除了源點和匯點每一個點流量平衡。

假設源點為 \(S\)，匯點為 \(T\)。

則我們可以加入一條 \(T\) 到 \(S\) 的上界為 \(\infty\)，下界為 \(0\) 的邊轉化為無源匯上下界可行流問題。

若有解，則 \(S\) 到 \(T\) 的可行流流量等於 \(T\) 到 \(S\) 的附加邊的流量。

給定有源匯流量網絡 \(G\)。詢問是否存在一種標定每條邊流量的方式，使得每條邊流量滿足上下界同時除了源點和匯點每一個點流量平衡。如果存在，詢問滿足標定的最大流量。

我們找到網絡上的任意一個可行流。如果找不到解就可以直接結束。

否則我們考慮刪去所有附加邊之後的殘量網絡並且在網絡上進行調整。

我們在殘量網絡上再跑一次 \(S\) 到 \(T\) 的最大流，將可行流流量和最大流流量相加即為答案。

一個非常易錯的問題

\(S\) 到 \(T\) 的最大流直接在跑完有源匯上下界可行的殘量網絡上跑。

千萬不可以在原來的流量網絡上跑。

給定有源匯流量網絡 \(G\)。詢問是否存在一種標定每條邊流量的方式，使得每條邊流量滿足上下界同時除了源點和匯點每一個點流量平衡。如果存在，詢問滿足標定的最小流量。

類似的，我們考慮將殘量網絡中不需要的流退掉。

我們找到網絡上的任意一個可行流。如果找不到解就可以直接結束。

否則我們考慮刪去所有附加邊之後的殘量網絡。

我們在殘量網絡上再跑一次 \(T\) 到 \(S\) 的最大流，將可行流流量減去最大流流量即為答案。

對於每條 \(x\) 到 \(y\) 花費 \(v\) 的劇情邊設上界為 \(\infty\), 下界為 \(1\)。

對於每個點，向 \(T\) 連邊權 \(c\), 上界 \(\infty\), 下界為 \(1\)。

\(S\) 點為 \(1\) 號節點。

跑一次上下界帶源匯最小費用可行流即可。

因為最小費用可行流解法與最小可行流類似，這裏不再展開。

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用