生成樹

MST？Kruskal過程：貪心、重構樹

prufer序列：一般樹，森林，有根樹，用于DP或者打暴力

Matrix-Tree定理：給定圖求生成樹個數，鄰接矩陣數字表示邊權

多次求MST或者多次加邊等等：考慮縮點

一些圖的問題：找到生成樹處理（如Tarjan的dfs樹，支配樹，最短路樹）

1.[Ctsc2014]圖的分割?

考慮Kruskal的過程，發現恰好可以直接貪心！

2.51Nod1446?限制價值樹?

兩部分，折半枚舉合法集合，統計生成樹個數

3.

最小生成樹計數：排序kruskal時候，縮點配合矩陣樹

4.[APIO2013]道路費用?

還是枚舉哪些邊會最終貢獻，為了提高效率，進行縮點

5.[HNOI2010]城市建設?

cdq分治，把一定不會在最小生成樹的邊提前刪掉，一定在的提前加上。其實還是縮點提高效率

最短路

常用dij和floyd（spfa）

考慮某些邊、點和最短路關系，往往需要統計每個點開始、結束的最短路信息

還有一些建超級匯的操作

最短路樹，最短路DAG，或者任意某條最短路都可以做文章

兩個源匯的確切路徑，考慮分層分步

例題1

你在一個國家旅游，國家可以看做有向圖
? 每一條邊都有過路費
? 在每一個點，你可以選擇花費 ?? 購買魔法棒，當你持有魔法棒時，
你所經過的所有邊都會永久免費（第一次也不需要付錢），但是
最后你必須把魔法棒放回這個點
? 你可以無限購買魔法棒

每個SCC至少購買一個魔法棒

? 求能經過盡量多的城市的前提下，你所花費的最小代價

?

求SCC，topoDp

對于每個SCC，要知道從某個點開始，走若干個邊，然后買魔法棒的最小花費

買魔法棒就停止了，可以當做終止節點

多起點多終點？

每個終點向T連接pi的邊，然后從T跑最短路即可

?

?例題2

? 給出一張圖，每個點上有很多人，每條邊上也有很多重邊
? 設一個點的重要程度為

Pr表示概率

? 求每個 v?
? ? ≤ 3000, ? ≤ 10000 Vp = §,

cnt(a,b)表示a到b的最短路徑條數

直接的式子是枚舉p再枚舉a，b，O(n^3)

考慮能不能“繼承點東西”降低復雜度

?

具體地，枚舉A，給所有的p貢獻可能的B

對于A，求出A的最短路徑DAG

對于一個p，p能到達的節點B，AB的最短路，p都是可行點

但是cnt(p,b)不能分離，看起來還是3次方的

發現，p后面的DAG，恰好一定也是p的最短路徑DAG的一部分！

所以倒序topo，每個點T有一個權值T/cnt(A,T)，后繼貢獻直接加起來，cnt(p,b)自然就得到了

例題3:

? 給出一張 DAG，求出有多少點對 ?, ?，使得任意從 ? 到 ? 的路徑

都恰好經過 ?, ? 中的任意一點

? ?, ? ≤ 100000

考慮兩個點a，b合法的充分必要條件：

1.a，b互不可達

2.cnt[s][a]*cnt[a][t]+cnt[s][b]*cnt[b][t]=cnt[s][t]

topo搞到拓撲序和cnt,

把val[*]=cnt[s][*]*cnt[*][t]進行離散化，開值域個bitset

倒序考慮拓撲序，枚舉a

bitset處理可以到達的集合S

得到val[b]的值，S取反，和這個val[b]的bitset取交，交的個數就是貢獻

然后把val[a]的a位置設置為1

這樣就保證了a，b互不可達

例題4

給出一棵樹，邊權為正
隨機選出 ? 個關鍵點，然后選擇一種移動總距離最短的方案，從
其中某個點出發，經過每個關鍵點至少一次
求出移動總距離最短的方案的期望
? ≤ 500

?

總距離最短：虛樹總邊長*2-直徑

虛樹總邊長*2：考慮邊的貢獻，兩邊一共選擇k個

直徑：支持單點增量

不妨直接枚舉直徑(a,b)，考慮對應的點集個數

如果(a,b)加入p之后合法，也即max(dis(p,a),dis(p,b))<dis(a,b)，那么p可以加入

這樣從所有能加入的p中選擇k-2個即可得到所有的方案數

但是一個虛樹多個直徑可能算重

方法：

每個邊(u,v)不妨u<v ，有額外權值：2^(-u)，

這樣，一個虛樹直徑一定會在字典序最小的位置被求恰好一次，就完全分開了

例題5

給出一張有向圖，每條邊上有數字
對每一對點對 ?, ? ，求從 ? 到 ? 的最短的回文路徑
? ≤ 500, ? ≤ 10^5

類似[HNOI2019]校園旅行

分成兩步走

f[a][b]表示a到b的最短路

每次讓a走一步

g[a][b][char]表示該b走了，a上一步走的字符是char的最短路

例題6

CF1163F Indecisive Taxi Fee

刪邊最短路

?

差分約束

如果能從題目中找到二元一次不等關系，即可差分約束

可以求一組最值解或者判斷有無解

是數形結合的思想

可能無解，所以時而還配合于二分

?

例題1

?51nod地鐵環線

可行的總長是一段區間

考慮二分總環長+SPFA判定

?先找右端點，再找左端點，

問題是不合法的時候mid是大還是小

以最短路為例，x=mid

每個邊權值可以看做：kx+b

如果一個負環總和為Kx+B<=0

根據K的正負即可判定x過大還是過小

K=0顯然就無解了。

例題2

THUSC2018

圓環上有 ? 對藍點，每一對藍點之間連了一條強度為 ?? 的線段
你需要在切割若干次，每次是用一條直線切割所有經過的線段
如果一條線段被切割超過 ?? 次，它就壞了
求至少要切割幾次
? ≤ 3000, ?, ?? ≤ 10000

每個線段兩側都至少>=k個切割點

對于所有的切割點，i和i+tot/2進行連邊

每個線段也會恰好被切割k次

同上題

甚至直接二分即可，不用Kx+b

拓撲排序

DAG是具有優美性質的圖

topo排序是分層圖的思想

topo序的先后含有一些到達關系

例題1

給出一張無向圖
求一個最大的子圖，使得每個點的度數都不小于 ?
? ≤ 10^6

不斷刪除度數小于d的點即可

例題2

兩個人在 DAG 上走，每個人都有自己的起點和終點
求兩個人不經過一條邊的方案數（這里不經過同一條邊指的是：路徑的邊沒有交集）
?, ? ≤ 1000

類似：[HNOI2019]校園旅行

還是分層變成回合制。使得多了一些可以共用的中間狀態

f[a][b]表示達到(a,b)的方案數

每次topo序小的先走

不經過同一條邊？不能連續(i,i)->(j,j)

所以，中間變量g[a][b][0/1]表示一個走到a，一個走到b，上一次是否位置相同的方案數

O(nm)

例題3

[POI2014]RAJ-Rally

topo序好題

?

2-SAT

?[學習筆記]2-SAT?問題

命題蘊含關系

各種優化建圖

例題1

【UER #6】尋找罪犯

最難辦的是：最多說一句謊

只給每個犯人開兩個點

每個犯人處理：他說的，和說他的

1.他是犯人

說他不是犯人的都是犯人

說他是犯人的人，只說了這一句謊，所以這些人的說的其他話都是真的。暴力連邊O(m^2)前綴后綴優化即可

2.他不是犯人

說他是犯人的都是犯人

他說的話都是真的

?

Tarjan求方案即可

?

網絡流

過于博大精深

度數回路上下界：先走完限制，再調整

范圍較小的值域限制：切糕割

且關系的收益，或關系的花費：每個關系建新點

二元或關系的收益，且關系的花費：隔斷含義反轉，二元關系最小割。（前提：涉及的點對構成二分圖（這個“點”也可以是集合的且，詳見例題4））

一些依賴的帶點權最大化問題：最大權閉合子圖

匹配問題的DP：網絡流的匹配關系可以優化DP，否則只能狀壓DP

如果有些東西一定會被計算：整體+權值可以把負權變成正權

各種網格、橫縱等：都具備一定二分圖性質，翻轉連邊，匹配

還有一些特殊題型和翻轉

例題1

給出一張無向圖，每條邊有一個次數限制
你需要找一條總長度盡量短的可以不是簡單路徑的回路，使得它
經過每條邊至少那么多次
? ≤ 500

直接干掉下界

回路？每個點度數為2

兩點之間走一條路徑，只會使得起點終點度數奇偶改變

考慮奇度數節點，兩個奇度數節點之間連接距離長度的邊權

找一個最小權完美匹配即可

例題2

給出若干個定義在[0, ?] 的分段一次函數
請你把這些一次函數分成最少若干個組，使得每個組內的一次函數兩
兩不相交

n<=250

不相交關系，形成DAG，求最小鏈覆蓋即可

例題3

文理分科

經典且或關系問題

例題4

有一個網格，每個格子你可以決定買不買
如果你買了一個格子，就要花費其價格
如果你買了一個格子，或者買了和這個格子相鄰的所有格子，你
可以獲得這個格子的收益
最大化收益減去價格

n,? ≤ 100?

或有貢獻，發現正是二分圖！

含義反轉，貢獻關系單獨表示成點

本質上還是兩個“點”的或關系，一個滿足有收益

這樣建圖：

黑白染色成為左右部點

ans+=所有收益

S到左部點cosi，右部點到T連cosi

由于共同收益和單點購買的收益一樣，所以每個點像上圖一樣連好關系

這樣只要左邊都選，或者這個點選擇，那么這個收益就可以保留，否則收益必須割掉?

?

例題 5

[校內練習]Trip

例題 6

彎彎國

? 給出一張網格圖，網格上有一些障礙
? 你需要給每個沒有障礙的網格放一個恰好連接網格的兩條邊的軌
道，同時使得這個軌道的兩端都和其他軌道的兩端相連
? 在一些格子里生活著一些彎的人，他們希望能讓自己所在的格子
里的鐵軌是彎的
? 求最多能滿足多少彎人的要求
? ?, ? ≤ 50

有點類似「清華集訓 2017」無限之環

把所有彎的貢獻都加上

直有花費

彎？一個向上下，一個向左右

直？都向上下，或者都向左右

拆邊費用流！

上面兩個點連接上、下

下面兩個點連接左、右

這樣直一定有懲罰，彎不會有懲罰！

最小費用最大流！

例題7

真實·網絡流優化DP

? 在樹上選出兩個盡量大的不相交的同構的連通塊
? ? ≤ 50

同構？
枚舉邊
一半的根就是邊的端點，枚舉另一半的樹根
有根樹，f(i,j)i為根，j為根的最大連通塊，對于du^2的兒子進行帶權最大匹配

O(n^7)
發現，可以記憶化!
因為另一半樹根變化，其他的邊只是方向變化
f(e,j）一半邊e（帶方向），確定根的一半的j的子樹
可以記憶化
O(n^6)

非常不完全n^6，可過

例題8

在地圖上有一些敵人，每個敵人有一個消滅可獲得的價值
地圖上還有很多的發射器，每個發射器有最大的射程限制，同時
有一個朝向，保證沒有面對面的發射器
你可以對每個發射器指定一個射擊距離，這個發射器就會消滅發
射器朝向的這個方向的、距離恰好為這個射擊距離的敵人，但是
要求兩個發射器射擊時經過的格子不能相交
求最多能消滅多少價值的敵人

?, ? ≤ 50

范圍很小，還有限制，考慮切糕割

但是這里的收益很難都算上然后扣去

但是由于每個發射器都要發射一定是最優的

所以每個邊的流量是-v(i,j)+M，M是這一行的價值和

考慮用inf邊限制不能相交，只用考慮橫和縱

若x>=a,則y<b,若y>=b則x<a

如果連邊都是同一個方向，一個更小反而不合法

由于橫縱二分圖，把橫反過來連邊

即可

?

例題9

給出一棵樹，然后給樹上每一條邊染色，要求每個點的出邊顏色
互不相同
? 最小化每條邊所染顏色的編號和
? ? ≤ 150

設f[i][c]以i為根子樹，father到i的邊的顏色是c的最小編號和

顏色互不相同？匹配！

枚舉f[i][c]

S-每個兒子-分別連每個顏色c+f[soni][c]的邊-每個顏色連到T邊權為1

最小費用最大流

O(n*m*dinic）

?

例題10

? 給出一張無向圖
? 請你往圖上加一些邊
? 加完邊后，設點 ? 的距離是dp，那么總得分是 ∑c(p,dp)
? 最大化得分

? ≤ 50

其實最后只要滿足，對于原來有邊相連的點對(x,y)最后必然有|disx-disy|<=1

所以切糕割即可

一定有一種方案還原

例題11

[CQOI2014]危橋

另類網絡流

?

例題12

給出一張無向圖，每條邊有一個經過時間
? 現在有 ? 個乘客，它們分別在第 ?i個點，并且都想前往點 1
? 所有人都只想走一條最短路，并且同時從起點出發
? 如果兩個人同時同向經過同一條邊，那么堵塞了，不合法
? 請你求出一個盡量大的乘客的子集，使得不會出現擁塞

找最短路徑圖
最短路不同，不會堵塞
對于最短路相同的所有人，分別跑一遍最大流

?

轉載于:https://www.cnblogs.com/Miracevin/p/10851212.html

總結

以上是生活随笔為你收集整理的[题集]图论的全部內容，希望文章能夠幫你解決所遇到的問題。

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