图论 —— 网络流
【概述】
網(wǎng)絡(luò)流是一個(gè)適用范圍極廣的模型，相關(guān)的算法也很多，大體分為最大流、最小割、費(fèi)用流三類。
對(duì)于網(wǎng)絡(luò)流類型的題來說，一般根據(jù)題意，分析后建出圖后，套用相關(guān)模版，即可解決問題。
關(guān)于網(wǎng)絡(luò)流的基本概念與建模技巧：點(diǎn)擊這里
【算法】
1.最大流算法
求最大流算法分為兩類，一種是增廣路算法，一種是預(yù)留推進(jìn)算法。
增廣路算法，常用的有時(shí)間復(fù)雜度 O(n*m*m) 的 FF 算法、EK 算法，上界為 O(n*n*m) 的 Dinic 算法，以及對(duì) Dinic 進(jìn)行改進(jìn)的 ISAP 算法；壓入與重標(biāo)記算法又稱預(yù)留推進(jìn)算法，其時(shí)間復(fù)雜度為 O(n*n*m)
- FF 算法與 EK?算法：點(diǎn)擊這里
- Dinic 算法：點(diǎn)擊這里
- SAP 算法與 ISAP 算法：點(diǎn)擊這里
- 壓入與重標(biāo)記算法：點(diǎn)擊這里
2.最大流最小割
求最大流的最小割時(shí)，根據(jù)最大流最小割定理，可以在求最大流的過程中求出最小割，一般常用的是?Dinic 算法。
- Dinic 算法：點(diǎn)擊這里
若網(wǎng)絡(luò)流的圖是一個(gè)平面圖，那么可以將其轉(zhuǎn)為對(duì)偶圖，然后跑最短路算法
- 平面圖與對(duì)偶圖：點(diǎn)擊這里
若要求最大權(quán)閉合子圖，可以轉(zhuǎn)為最小割問題，然后利用 Dinic 來解決
- 最大權(quán)閉合子圖：點(diǎn)擊這里
若要求最大密度子圖，那么需要利用 01 分?jǐn)?shù)規(guī)劃來分析，從而轉(zhuǎn)換模型
- 01 分?jǐn)?shù)規(guī)劃：點(diǎn)擊這里
3.費(fèi)用流
一個(gè)網(wǎng)絡(luò)流圖中最大流的流量是唯一的，但是達(dá)到最大流量時(shí)，每條邊上的流量分配是不唯一的。?
若給網(wǎng)絡(luò)流圖中的每條邊都設(shè)置一個(gè)費(fèi)用 cost，表示單位流量流經(jīng)該邊時(shí)會(huì)導(dǎo)致花費(fèi) cost，那么在這些流量均為最大流的流量分配 f 中，存在一個(gè)流量總花費(fèi)最小的最大流方案。
即：min{sum(cost(i, j)*f(i,j)}，其中 cost?(i, j) 屬于方案 f 中的邊，f(i,j) 為邊 (i,j) 上的流量，f 為某一個(gè)最大流方案
求解最小費(fèi)用最大流最常用的算法是基于 SPFA 的 MCMF 算法：點(diǎn)擊這里
由于 MCMF 算法是基于是 SPFA，而有時(shí)會(huì)卡 SPFA，因此除 MCMF 外，還有基于 Dijkstra 費(fèi)用流：點(diǎn)擊這里
除以上兩種求費(fèi)用流的方法外，還有一種更為高效的費(fèi)用流算法，即 zkw 費(fèi)用流：點(diǎn)擊這里
【例題】
除例題外，可參考?Edelweiss 的《網(wǎng)絡(luò)流建模匯總》，具體內(nèi)容：點(diǎn)擊這里
1.最大流
2.最小割
3.費(fèi)用流
總結(jié)
- 上一篇： 基础算法 —— 调度问题 —— 流水调度
- 下一篇： 字符串处理 —— 回文串相关 —— Ma