一些有难度的网络流问题
- 本質是線性規劃
最小割建模
NOI2010 海拔
- 一個的網格，每跳變的兩個方向都有一定數目的人流，每個格點都有海拔，一個人爬坡需要付出高度差的代價，下坡不付出代價，左下角高度為，右上角高度為，求安排其它點蓋度最小化總代價。
對偶圖+Dijikstra
調整法證明高度一定是01且構成一個割。
TCO Semifinal Colorful Tree
- 一個DAG，保證邊一定滿足，且邊的區間一定只存在包含不存在相交，每個點都有一個顏色，每種顏色要不全都經過要不全都不經過，邊有邊權，求最短路
邊區間不相交構成一棵樹，其實就是原圖對偶圖，最短路轉化為最小割，
連若干inf邊保證同色點在一邊，向父親連inf保證形態。
最大權閉合子圖
有個物品，每個物品有一個價值（可負），你需要選出一個物品的集
合，最大化其中物品的總價值，并滿足個限制：選了就必須選
擇。?
正價值物品與連邊，負價值物品與連邊，使用容量無窮的邊來限制選
了就必須選擇。
完美理論
- 給定兩個編號都是1到N的樹，你需要選的一個子集，最大化選到的元素權值（可負）的和，同時你選的集合在兩棵樹上都是連通子圖
枚舉根，選x必須選x的父親，最大權閉合子圖。
SRM 577 HardBoardPainting
- 一個有障礙的網格，每次粉刷一橫列或者一縱列，不可重復粉刷，求最少的粉刷次數粉刷所有非障礙路。
考慮兩個點是橫著被刷還是豎著被刷
極小割對應涂色法，極小割對元素有唯一劃分，與橫邊界相連的橫涂與縱邊界相連的縱涂。
每個格子當成變量，表示橫向粉刷這個格子， 表示縱向粉刷，橫著相鄰的兩個格子若在同一個集合就可以一起粉刷獲得收益，縱向亦然。最大權閉合圖模型。
另一種做法：鏈接所有相鄰的各自，從橫向邊界到縱向邊界做最小割，除以二就是答案
證明：涂色法對應割，一條染色用割掉兩端的邊表示
極小割對應涂色法，極小割對元素有唯一劃分，與橫邊界相連的橫涂與縱邊界相連的縱涂。
集合劃分模型
- 考慮如下的整數劃分
- 即除了每個元素取0,1會有代價的差異之外，若兩個變量取值不等則會付出額外的代價，且根據誰選擇1代價可變。
- 根據的取值把元素劃分成兩個集合，可以容易的建立出最小割模型，采用最大流求解。
- 集合劃分模型只處理不同集合的元素對之間的代價，若要相同集合付出代價，需是二分圖黑白染色后處理。
?
SRM 594 Medium FoxAndGo3
- 一個圍棋棋盤，任意兩個白子不相等，你要加入若干個黑子并提出白子，最大化空格數目
注意到與白子與相鄰的空格最終不可能都為空格，于是連邊，接著做最大點獨立集，顯然是二分圖。
最優選擇
- 給出一張個點的無向圖，每條邊的邊權定義為所鏈接兩點點權的異或（異或的性質：每一位獨立），有些點權確定，有些沒有，請確定所有點的點權，使得邊權和最小
每一位分開考慮，除固定權值外，此位置不同才付出代價，集合劃分模型。
SRM 558 Hard Surrounding Game
- 一個人在一個的棋盤上面放棋子，在放棋子有的代價，一個各自被占領當且僅當其上有棋子或者其所有相鄰格子都有棋子，被占領會獲得的收益，求最大收益(注意要減去代價)
每個格子建立兩個點，第一個點表示是否被占領，第二個點表示周圍格子是否全部被占領，為避免重復統計收益，還要黑白染色厚在這兩個點之間要連邊。
離散變量模型
離散變量型網絡流一般解決如下問題：
SRM 590 Hard FoxAndCity
- 一張個點的無向圖，邊權都為，你需要添加若干條便，最小化，是輸入的，是1號點到i的最短路
比較經典的建模姿勢
有邊相連意味著
于是可以每個點拆出一排點。
就是離散變量，顯然加邊不可能讓最短路變長，同時原本就有邊的兩個點最短路差不超過1.
SRM627 Hard LaserTowers
- 你有一個的矩陣，有些位置有方向固定的激光塔，激光塔能選擇這個方向的一個敵人攻擊，每個敵人有一個收益，兩個激光塔的激光不能相交，求最大收益
對于一個圖限制轉彎次數（特殊邊的經過次數）
有一個通用方法：拆點
每一點拆為橫點和豎點
轉化為最小割
離散變量為第幾個敵人，橫向到縱向的割，拆點保證不轉多次彎。
BJOI2016 水晶
- 六邊形網格中如圖分布著能量源，還有個特定位置的水晶（可在能量源上），你需要炸掉一些水晶石得剩下的水晶不能組成三元環且沒有兩個水晶分列一個能量源的兩側，最大化剩余水晶的權值和。
考慮每個在能量源的水晶，把無能量源的點黑白染色，則要不炸掉能量源，要不炸掉全黑，要不炸掉全白，離散變量有三個取值，S=val>白=inf>A=1.1val>B=inf>黑=val>T。
最大流&&費用流
技巧主要有：
?????? 拆點
?????? 容量限制
?????? 流量平衡
?????? 建立超級源匯
?????? 動態加點
?????? 線性規劃不等式變形（比如差分）
?????? 線性規劃轉對偶
?????? 流量分配
?????? 匹配與拓展
?????? 流量平衡
?????? 歐拉回路
?????? 帶上下界的網絡流
?????? 線性規劃與對偶
流量分配
??? ?一般是把點上的要求變成流量。
??? ?入流和出流的對接表現方案。
?
SCOI2012 奇怪的游戲
- 給出一個的棋盤，每個格子上有一個數，可以給相鄰的兩個數同時，相鄰指有公公便，求最少多少次操作可以將棋盤上的數變為同一個數，如果不可能輸出.
對原棋盤進行黑白染色。設黑色格點有個，數值和為；白色格點有個，數值和為。設最后所有的數都變成了x，則有：
，即：
。
I.? 若，那么就二分答案并檢驗。
II. 若，那么只需要保證：
? 1)
? 2) x >= 棋盤中的最大數；
? 3) 能通過最大流的檢驗。
網絡建模時，從S點向白色格點建邊，流量為x減去格點上的數；從黑色格點向T建邊，流量為x減去格點上的數。另外從白色格點向上下左右建邊（不超出邊界），流量為正無窮。
若求出來的最大流的二倍剛好等于所有格點需要被加上的數的總和，那么此x滿足條件，否則不滿足條件。
Turning Railways
- 一個的有障礙棋盤，用回路覆蓋所有空白格子，最大化有轉彎的格子數目
每個點的理想情況是橫著一條邊豎著一條邊
每個點拆成兩個點
橫點指向橫點，豎點指向豎點
橫點豎點之間連一條容量為1，費用為1的雙向邊
然后跑最小費用最大流
用原答案減去費用流即可
總之：黑白染色，每個點拆兩個點分別表示橫縱，中間建一條邊表示違反代價。
SRM 575 Hard TheTilesDivOne
- 你要在的有障礙的網格上放盡量多的L型瓷磚（3個非直線連續格子），不能互相覆蓋也不能覆蓋到障礙，且重心格子必須在黑格子上（黑白染色）
- （據lzz所說有個出題人特別喜歡47來著）
對剩余白格子再進行紅藍染色，則一個L為紅→黑→藍，最大流模型。
集訓隊訓練D1T2
- 的網格圖，里面有一些水管
- 水管可以有很多頭（2~4個），其中直線的水管不可以轉，別的水管都可以以1的代價旋轉90度，可以順時針或者逆時針轉
- 最小化旋轉次數使得沒有水管頭
L型一個行點一個列點
T字給每出邊一個不選的損失。
匹配和拓展
- 二分圖匹配
- 路徑覆蓋
- 匹配的存在和唯一性
- 匹配問題的對偶
Codechef SEPT 12 PARADE
- 個點，條帶權單項道路，若干個英雄需要在其中游行，游行可以是路徑也可以是賄賂，除了要付出路徑的權值外，一個點弱沒被任何英雄經過，則要付的代價，另外如果一個英雄走的是路徑，也要付出的代價送他回家，求最小代價，有個不同的
路徑覆蓋→二分圖匹配，發現額外代價=C(n-flow)。
K-完備匹配
??? ?給出一個有個點的二分圖
??? ?問是否存在個不相交的完備匹配
??? ?不相交的匹配是指對于同一個節點，每一個匹配中匹配的節點均不相同
??? ?
??? ?Hall定理：若二分圖每個點度數均為k則存在k-完備匹配
??? ?流量分配求k-正則二分圖子圖
?
Problem Buyer
- 有個題目的題庫，每個題的難度為，從中出個題目，第i題難度需要在和之間
- 求最小的使得對于任意一個個題目的子集都能湊出一套符合要求的題
很顯然k具有二分性質，所以先二分k
霍爾定理，顯然是選一個難度區間內的題目最可能不滿足，掃描線+線段樹維護。
硬幣游戲
- 一個的有障礙的棋盤，兩個人輪流移動，不能走重復的位置，不能移動的數，問那些位置是先手必勝的
這個叫做二分圖博弈
如果在最大匹配上就先手必勝
在每個點上面直接BFS/DFS即可,也不會超時
可以做到O(N+M)?沒有聽懂
PS：搜集到一題BZOJ1443游戲，下次可以做一下
ChessBoard
- 的棋盤上擺了個車，且他們兩兩不相互攻擊。
- 第i個車必須擺在一個矩形里
- 求哪些車的擺放位置是確定的？
顯然匹配，往右保留未匹配邊，往左保留匹配邊，tarjan縮強連通分量。
BZOJ3118
- 一個無向圖，每條邊可以花費的代價權值+1，也可以花費的代價權值-
1，你需要使得一個指定的樹的權值等于最小生成樹，問最小花費。
每條非樹邊對其覆蓋的所有樹邊都有一個不等式。
相當于頂表和，轉對偶到匹配。
流量平衡
流量平衡時費用流模型
就是利用每個點流入流量等于流出流量來滿足等式，如果流入流量-流出流量=常數，可以通過與源點和匯點連邊來實現
混合圖的歐拉回路
給一個混合圖讓你給無向邊定向并求出歐拉回路
消負環
- 可以使用流量平衡來消負環
- 首先每個點拆成,兩個點
- 對于邊，建立，再對于每個點，建立
- 這樣做最小費用最大流可以保證每個點的入度等于出度，即若干個環
China-FINAL16 Mr. Panda and TubeMaster
- 在的網格圖里找若干個環，每個點都必須是轉角，最大化邊權和
最小費用流消負環--->最大費用流消正環
WF2011 Chips Challenge
- 在一個的網格里面放部件，其中有一些格子已經放置，有一些格子損壞。要求第x行的部件數目等于第x列，同時要求任意行和列的部件數不超過總數的
二維模型+流量平衡限制，枚舉每行每列部件數限制即可。
歐拉回路
- 求無向圖的歐拉回路
- 可以dfs直接定向（網上有板子可以直接找一下）
?
混合圖歐拉回路
- 給一個混合圖你要給無向邊定向并求出歐拉回路。
- 先隨便定向，建立超級源匯，流量平衡保證出入度平衡。
?
CF 547D Mike and Fish
- 有一些點請你對點黑白染色，使得每行每列都滿足黑點和白點數目差不超過1
考慮行列建點，每個點變成邊。?
如果是歐拉圖，那么每個點的入邊=出邊，考慮每一個行點，把入邊都染成黑色，出邊都染成白色那么就一樣多了。?
但是有可能一開始不是個歐拉圖（有點的度數為奇數），我們可以對度數為奇數的點兩兩配對（一定有偶數個），然后就一定是個歐拉圖了。跑無向圖輸出歐拉回路即可。?
CF 429E Point and Segments
- 有一些區間請你對這些區間黑白染色，使得每個點覆蓋它的區間中黑白顏色數目之差不超過1
lzz貌似建議去做IOI的題目（逃
每個區間可以看成從l到r+1的一條邊，一端++一端--，方向對應加減。
歐拉回路？差不超過1怎么處理。
相鄰的奇數點加邊匹配。
UNR #3 D2A. 轉圈
- 給一個平面上的無向圖，請你走一個歐拉回路，最小化總共轉過的角度？
引出一條射線，逆時針傳過權值-1，順時針傳過權值1，最大費用流。
給邊初始定向然后通過流量分配來解決，定向保證沒有負權邊。
帶上下界的網絡流
- 建立超級源超級匯，由下界計算出每個點冗余/虧損多少流量，用和超級
源匯連邊實現。 - 用新圖的流量平衡保證原圖流量平衡，注意要在原圖上建立到的邊。
UNR #2 D2B. 奇怪的線段樹
- 給一根任意分治（輸入給定）的線段樹，一個區間有唯一的拆分方法，一個節點會染黑它拆分出來的節點。
- 現在你需要使用最少的區間把指定的節點染黑
一個區間拆出來的一定是若干個連續右孩子+若干個連續左孩子
把樹建成DAG然后是指定覆蓋，用下界最小流做。
區間選擇
- 給出 個區間（值域），選擇第個區間會得到收益
- 數軸上每個點最多只能被k 個區間覆蓋
- 要求選出一些區間，使得收益最大
從左向右連一條容量k 的鏈，區間從左端點到右端點連邊。
NEERC 16 Delight for a Cat
- 一只貓有天，第天選擇吃飯可以獲得，選擇睡覺可以獲得，連續k天至少睡覺天，至少睡覺天，最大化收益
不妨假設全部睡覺，從到 連邊容量為，若走這條邊表示今天改為吃飯。總流量上限為 表示最多吃飯的天數，從 到連邊容量為表示之前k 天至少選擇 天吃飯否則達不到最大流量，最小費用最大流建模。
NOI2008 志愿者招募
這題被lzz咕掉了
?
總結
以上是生活随笔為你收集整理的一些有难度的网络流问题的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 蓝桥杯 省赛真题寻找 2020
- 下一篇： 家族关系查询系统程序设计算法思路_数据结