上下界網絡流

2021.9.3

無源匯上下界可行流

之前的最大流討論一般為有源無下屆情況，那么無源匯有上下界可行流應如何求解？

首先要做的是消除下邊界，應如何做？在有下屆情形下，流網絡中的任意一條邊的可行流應滿足$fmin(u,v)\le c(u,v)\le fmax(u,v)$,由此可變換公式得$0\le c(u,v)?fmin(u,v)\le fmax(u,v)?fmin(u,v)$，此時，構建的流網絡中邊的下屆均為$0$.

但是，此時引入了新的問題：流量是否守恒？絕大部分情況下，不守恒。新網絡中，由上方公式構建的可行流，排除下屆后守恒，但是有如下情形:設當前點為$i$，入邊為$j$，出邊為$k$,若${\sum }_j^{j?edge[i]}fmin(j)!={\sum }_k^{k?edge[i]}fmin(k)$ ，則此時總流量不守恒。

如何解決？已知本題類型為無源匯，因此每個結點，都可理解為一個源頭。但不能直接從結點加入流量，若直接從結點算作無限流量，則無法保證整條路中的流量守恒。

此時可加入一個虛擬源點$S$和一個虛擬匯點$T$，當一個結點i的入邊下屆小于出邊下屆，便從源點$S$向i連接一條最大流量為${\sum }_j^{j?edge[i]}fmin(j)?{\sum }_k^{k?edge[i]}fmin(k)$ 的邊，當$i$的入邊下屆大于出邊下屆，便從$i$向$T$連接一條最大流量為${\sum }_k^{k?edge[i]}fmin(k)?{\sum }_j^{j?edge[i]}fmin(j)$ 的邊，由此保證了整個網絡的流量守恒$?$流量中每條邊的流量之和等于每個結點產生的流量，此時可把每個點產生的流量轉移到我們自行添加的虛擬源點之上。

代碼

cin >> n >> m; S = 0, T = n + 1; memset(head, -1, sizeof head); for (int i = 0; i < m; i++) {int a, b, c, d;cin >> a >> b >> c >> d;add(a, b, c, d);A[a] -= c, A[b] += c; } int tot = 0; for (int i = 1; i <= n; i++) {if (A[i] > 0)add(S, i, 0, A[i]), tot += A[i];else if (A[i] < 0)add(i, T, 0, -A[i]); }//上述add函數為 void add(int a, int b, int c, int d) {to[idx] = b, wei[idx] = d - c, l[idx] = c, nexte[idx] = head[a], head[a] = idx++;to[idx] = a, wei[idx] = 0, nexte[idx] = head[b], head[b] = idx++; }

這時候問題就轉化成了與https://blog.csdn.net/Tinberlake/article/details/119751664?spm=1001.2014.3001.5501上相同的有源求最大流問題，此時每個邊在原圖中的流量就是新圖中計算的流量加上其下屆流量$fmin(u,v)+c^{\prime }(u,v)$ 。

有源匯上下界最大流

此時的網絡中有源點，每個結點只能接受從源點匯來的流量，無法同無源匯上下界可行流一樣通過填補每個結點的流量進行計算。

此時如何求得網絡的最大流？此時，先將題目中的源點與匯點定義為$s$與$t$，另新建兩虛擬結點$S$與$T$，建立一條$t$到$s$可行流量為無窮的邊，此時先將問題轉化成了無源匯上下界可行流。

那么，為何從匯點到源點建立一條流量為正無窮的邊？保證流量守恒。

若要求最大流，則從$s$到$t$的流量一定為正，$0\le c(s,t)$ ，若要保證新圖與舊圖流量守恒的一致，則需要在$t$到$s$之間建立一條流量為無窮的邊。

那么，對于新圖中流量若小于從虛擬源點流出的最大流，則可證明沒有一條可行流滿足從$s$到$t$，此時存在邊不滿足下屆。

當新圖中的流量不小于虛擬源點流出的最大流，此時截斷從$t$到$s$流量為無窮的邊，并將此邊的逆邊流量記錄為$res$。將源匯點更改為$s$與$t$，那么，新圖中$s$到$t$的殘留網絡的最大流加上$res$即為有源匯上下界最大流的流量。

為何？新圖中無源匯的可行流構建了一個可行流，這個可行流最大時，代表所有結點的流量均守恒，此時的殘留網絡，若去除$t$到$s$之間流量為無窮的結點，則代表此時除去這兩點外，其余所有點的流量均守恒。這兩點作為源點與匯點，不必守恒，因此此時計算去邊后殘留網絡的最大流，可以保證整個網絡的流量是守恒的。又因為，新圖中原本$s$到$t$的不守恒流量的大小，就是被截斷邊的逆邊的流量，因此$s$到$t$的最大可行流就是$res$加新圖中$s$到$t$的殘留網絡的最大流。

代碼

cin >> n >> m >> s >> t; S = 0, T = n + 1; memset(head, -1, sizeof head); while(m--){int a, b, c, d;cin >> a >> b >> c >> d;add(a, b, d - c);A[a] -= c, A[b] += c; } int all = 0; for(int i = 1; i <= n; i++){if(A[i] > 0) add(S, i, A[i]), all += A[i];else if(A[i] < 0) add(i, T, -A[i]); } add(t, s, INF); if(dinic() < all) cout << "No Solution\n"; else{int ans = wei[idx - 1];S = s, T = t;wei[idx - 1] = wei[idx - 2] = 0;cout << ans + dinic() << '\n'; }//上述add函數為 void add(int a,int b, int c){to[idx] = b, wei[idx] = c, nexto[idx] = head[a], head[a] = idx++;to[idx] = a, wei[idx] = 0, nexto[idx] = head[b], head[b] = idx++; }

有源匯上下界最小流

根據有源匯上下界最大流的相關計算，可知若要$s$到$t$是最小流，則此時$t$到$s$的可行流最大，因此只需按有源匯上下界最大流建圖后，更改源匯點為$t$與$s$即可。

代碼

cin >> n >> m >> s >> t; S = 0, T = n + 1; memset(head, -1, sizeof head); while(m--){int a, b, c, d;cin >> a >> b >> c >> d;add(a, b, d - c);A[a] -= c, A[b] += c; } int all = 0; for(int i = 1; i <= n; i++){if(A[i] > 0) add(S, i, A[i]), all += A[i];else if(A[i] < 0) add(i, T, -A[i]); } add(t, s, INF); if(dinic() < all) cout << "No Solution\n"; else{int ans = wei[idx - 1];S = t, T = s;wei[idx - 1] = wei[idx - 2] = 0;cout << ans - dinic() << '\n'; }

總結

以上是生活随笔為你收集整理的上下界网络流-无源汇可行流与有源汇最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。