19.10.14馬上YC了，感覺自己看到簡(jiǎn)單網(wǎng)絡(luò)流題，都不敢以信心滿滿穩(wěn)切的心態(tài)去看題。
題目均來(lái)自洛谷網(wǎng)絡(luò)流24題。
題目列表：這里。

具體復(fù)雜度依照具體情況

• 最大流=最小割
• 二分圖最大匹配=最大流
• 二分圖的最小點(diǎn)覆蓋數(shù)=該二分圖的最大匹配數(shù)(最小點(diǎn)權(quán)覆蓋集==最小割)
• 二分圖的最小邊覆蓋數(shù)=圖中的頂點(diǎn)數(shù)-（最小點(diǎn)覆蓋數(shù)）該二分圖的最大匹配數(shù)
• 二分圖的最大點(diǎn)權(quán)獨(dú)立集=總權(quán)-最小點(diǎn)權(quán)覆蓋集(總點(diǎn)數(shù)-匹配數(shù))
• DAG最小無(wú)相交路徑覆蓋=原圖的結(jié)點(diǎn)數(shù)-新圖(拆點(diǎn)變成二分圖)的最大匹配數(shù)(如果求相交，那么floyd求出所有閉包，轉(zhuǎn)換為無(wú)相交）
• 最大權(quán)閉合子圖=正權(quán)值之和-最小割

以下S為源點(diǎn)，T為匯點(diǎn)。

P2756 飛行員配對(duì)方案問(wèn)題 //二分圖匹配

二分圖匹配板子，跑完后，看看$match$的值就好了。

P4016 負(fù)載平衡問(wèn)題 //費(fèi)用流

把大于平均值的放左邊，小于平均值的放右邊。
左邊右邊根據(jù)要轉(zhuǎn)移的數(shù)量拆點(diǎn)限流，費(fèi)用為0。
左向右連邊費(fèi)用為$min(順時(shí)針，逆時(shí)針)，$容量為無(wú)窮大。
在連上S和T。

P2763 試題庫(kù)問(wèn)題 //最大流

把種類到題目連起來(lái)流量為1，
題目到T流量為1，
S到種類流量為需要的題數(shù)。
跑最大流后看種類結(jié)點(diǎn)的出邊的$cap$有沒(méi)有被用掉就好(注意有到S的反向邊)。

P4014 分配問(wèn)題 //費(fèi)用流

人到工作流量為1費(fèi)用為$C_{i,j}$，S到人流量為1費(fèi)用為0，工作到T流量為1費(fèi)用為0，可以求最小。
將費(fèi)用取相反數(shù)，就可以求最大

P4015 運(yùn)輸問(wèn)題 //費(fèi)用流

倉(cāng)庫(kù)到商店連接起來(lái)容量$inf$，倉(cāng)庫(kù)和商店拆點(diǎn)限流（或者直接通過(guò)連接源點(diǎn)匯點(diǎn)限流

P2765 魔術(shù)球問(wèn)題 //二分圖匹配(最小路徑覆蓋

這題難度+++
假設(shè)現(xiàn)在有$x$個(gè)點(diǎn)，如果兩個(gè)點(diǎn)可以相加是平方數(shù)，那么小的向大的引一條邊。
問(wèn)題就轉(zhuǎn)換成了求DAG最小無(wú)相交路徑覆蓋（拆點(diǎn)二分匹配）。
DAG最小無(wú)相交路徑覆蓋$Z$：一個(gè)點(diǎn)拆成入點(diǎn)和出點(diǎn)，求最大二分圖匹配數(shù)，$Z$=頂點(diǎn)數(shù)-匹配數(shù)。
對(duì)于此題，可以二分，可以暴力逐個(gè)加點(diǎn)。
最后輸出的時(shí)候，因?yàn)楫?dāng)前網(wǎng)絡(luò)流里已經(jīng)把DAG分割成了$n$份，那么在DAG上面走，每次看網(wǎng)絡(luò)流里cap是否為零（是夠有匹配到），然后不停跳到匹配到的點(diǎn)。
其實(shí)用HA算法也OK的。

P2764 最小路徑覆蓋問(wèn)題

模板題，上一題K過(guò)了，這題就是順手…

P3358 最長(zhǎng)k可重區(qū)間集問(wèn)題//費(fèi)用流處理區(qū)間

這題思路巧啊。
大致知道是費(fèi)用流。
考慮將區(qū)間端點(diǎn)離散化，然后從小到大連成一條線$L$。
在$L$的前兩個(gè)點(diǎn)間限流$k$,其他可以不限流。
對(duì)于每一個(gè)開區(qū)間，$id[l]$到$id[r]$費(fèi)用為$?(r?l)$容量為1。
最后跑$min\_cost\_flow(L起點(diǎn)，L終點(diǎn))$。
保證$k$大小的流，且保證區(qū)間要么全取，要么一點(diǎn)都不取。

P3357 最長(zhǎng)k可重線段集問(wèn)題 //費(fèi)用流處理區(qū)間

這題和上一題不一樣的地方就是會(huì)有垂直于$x$軸的點(diǎn)，那么就會(huì)產(chǎn)生自環(huán)，那么這里考慮拆點(diǎn)。
拆成入點(diǎn)和出點(diǎn)，對(duì)于垂直于$x$的線段，入點(diǎn)到出點(diǎn)容量為1費(fèi)用為長(zhǎng)度，其他的都是出點(diǎn)到入點(diǎn)。
（得考慮建圖符合實(shí)際情況

P4011 孤島營(yíng)救問(wèn)題 //bfs+狀壓

原本的意思是：分層圖+最短路
BFS狀壓爆搜復(fù)雜度好像還低一點(diǎn)。（貪心撿所有鑰匙）$O(n?m?(1<<s))$

P3254 圓桌問(wèn)題 //最大流

隊(duì)伍和餐桌限流，然后構(gòu)建完全二分圖，跑完后看所有隊(duì)伍到餐桌的$cap$就行了

P4009 汽車加油行駛問(wèn)題 //分層最短路

$bfs$復(fù)雜度會(huì)爆炸，考慮分層建圖然后跑$dijkstra$，分成$k$層($1?n?n,n?n+1?n?n?2...$
每一層的層數(shù)表示當(dāng)前的油量，暴力建圖，連一個(gè)源點(diǎn)匯點(diǎn)跑最短路。
復(fù)雜度$O(n?n?k?log(n?n?k))$

P2762 太空飛行計(jì)劃問(wèn)題 //最大權(quán)閉合子圖

考慮 將所有與實(shí)驗(yàn)對(duì)應(yīng)的儀器向?qū)嶒?yàn)引一條邊，構(gòu)成一張DAG
那么答案就是最大權(quán)閉合子圖。
考慮用最小割求最大權(quán)閉合子圖：
S到每個(gè)正權(quán)點(diǎn)容量為權(quán)值，每個(gè)負(fù)權(quán)點(diǎn)到T容量為權(quán)值的絕對(duì)值，有向圖原來(lái)的邊容量全部為無(wú)限大，然后求最大流。
然后所有正權(quán)值的和-最小割就是答案(正權(quán)點(diǎn)-不要的正權(quán)點(diǎn)-要的負(fù)權(quán)點(diǎn))。詳細(xì)見這里
最后輸出的時(shí)候，看是否和S聯(lián)通即可，如果和S聯(lián)通（存在流量>0的路徑），說(shuō)明是要做的實(shí)驗(yàn)和遺棄。

P2774 方格取數(shù)問(wèn)題 //最大點(diǎn)權(quán)獨(dú)立集

可以發(fā)現(xiàn)把所有點(diǎn)分成二分圖。(所有回路都是偶數(shù)
發(fā)現(xiàn)這題求的就是二分圖最大點(diǎn)權(quán)獨(dú)立集(任意兩點(diǎn)不相鄰）= 點(diǎn)權(quán)和 - 最小點(diǎn)權(quán)覆蓋(最大匹配)(最小割)
假設(shè)全都取，再去掉最小割（使得沒(méi)有聯(lián)通）

P2766 最長(zhǎng)不下降子序列問(wèn)題//最大流

第一問(wèn)：暴力$lis$
第二問(wèn)：根據(jù)$dp$方程，從$dp[i]==1$的點(diǎn)作為源點(diǎn)，$dp[i]==s$的點(diǎn)作為匯點(diǎn)，對(duì)于每一個(gè)點(diǎn)拆點(diǎn)限流（保證只用一次。
根據(jù)轉(zhuǎn)移方程，對(duì)于$dp[i]+1==dp[j]\cap a[i]<=a[j]$的，引$i+n$到$j$容量為1的邊，這樣就保證到$dp[i]==s$的點(diǎn)長(zhǎng)度是$s$。
第三問(wèn)：放掉對(duì)點(diǎn)的限流（多加一條邊，再找殘余網(wǎng)絡(luò)）

P4012 深海機(jī)器人問(wèn)題

這里是邊上只能用一次（我想當(dāng)然的考慮把邊看成點(diǎn)，然后拆點(diǎn)限流，給我寫?了）
邊上只能用一次，那么將點(diǎn)連起來(lái)限流就好了…
最后對(duì)于出發(fā)和結(jié)束點(diǎn)連源點(diǎn)匯點(diǎn)限流。

P3355 騎士共存問(wèn)題 //最大點(diǎn)權(quán)獨(dú)立集

和方格取數(shù)差不多，這里求的也是最大獨(dú)立集。
這里先建圖(相互攻擊的連邊)。
可以發(fā)現(xiàn)所有攻擊回路都需要轉(zhuǎn)折偶數(shù)次，那么這是一個(gè)二分圖。
最大獨(dú)立集=點(diǎn)數(shù)-二分圖匹配數(shù)。
進(jìn)行二分染色，然后建最大流。
或者直接HA二分匹配。
答案就是$n?n?m?匹配數(shù)$

總結(jié)

以上是生活随笔為你收集整理的网络流(17/24)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。