圖論，其實是數學的一門分支，它以圖為研究對象。最基礎的圖論應該是著名的哥尼斯堡七橋問題，那是一個經典的一筆畫問題。
競賽中我們比較常見的是 最短路算法 最小生成樹算法 拓撲排序 等等。
本篇文章我們不說那些大家都懂爛了的圖論算法，講一些實用的 (沒什麼用的) 圖論小技巧。
鏈式前向星存圖
最最基礎的存圖的基本分為兩種，使用二維數組和使用 vectorvector ，但這兩種方法都有所缺陷。
使用二維數組查詢速度很快，但空間複雜度是 O(n2)O(n2) 的，一般的題目都接受不了。
使用 vectorvector 可以減少空間複雜度，但是時間就比較不確定了。
所以就出現了一種神奇的存圖方式，鍊表思想的鏈式前向星。
我們通常使用以下數組來完成
CodesCodes
新增加一條邊的時候我們進行如下操作
CodesCodes
用下面這種方式就可以枚舉出所有以 xx 為起始點的邊。
CodesCodes
大致思想就是將所有以 xx 為起始點的邊以鍊表的形式儲存，枚舉的時候遍歷鍊表，直到邊的編號為 00 (為 00 表示沒有其他的邊了)
這樣就可以滿足我們從某個點遍歷枚舉下個點的需要。
前向星鍊表被瘋狂應用在各個圖論題目中，基本上是一個圖論題都可以用到吧，屬於非常基礎的圖論技能。
需要注意的是對於雙向邊的題目，鏈式前向星的數組需要開邊數的兩倍，不然會 RERE 。
反向建邊
對於一個有向圖，某些問題中我們需要反向建邊來完成操作
比如求其他 nn 個點到 kk 點的最短路。
對每個點跑一遍最短路不就好了嗎？
事實上我們只需要跑一遍最短路就可以了，只需要把邊反向建。
反向建圖情況下 kk 點到每個點的最短路就是正常情況下該點到 kk 點的最短路。
例題 P1629 郵遞員送信
不只是最短路問題，在遍歷問題上也可以使用反向建邊來完成
例題 P3916 圖的遍歷
是否需要反向建邊，根據題意判斷即可。
反向建邊還可以來判斷某條邊是否在最短路上。
對於一個有向圖，我們從 11 號點跑一遍正向的最短路 dis[]dis[] ，從 nn 號點跑一遍反向的最短路 dis1[]dis1[]
如果 dis[x]+w(x,y)+dis1[y]=dis[n]dis[x]+w(x,y)+dis1[y]=dis[n] 那麼我們就可以得出，這條邊是在 11 到 nn 的最短路上的。
當然如果是無向圖的話直接跑就可以了。
虛點連邊
虛點連邊是一種很有效的優化建邊複雜度的方式
我們可能會遇見這樣一種題，給你幾個點，其他的點離這些給出的點的最近距離是多少。
我們可以對於每一個點進行 SpfaSpfa，但似乎這樣並不是很好操作。
我們可以自己給出一個點，然後向每個被標記的點連一條單向邊，這樣就只需要進行一次 SpfaSpfa 就可以了。
舉個例子，橙色為標記點，數字為最近距離。
例題 P3393 逃離殭屍島
但似乎這個直接廣搜也可以。
如果對於兩個點集 AA 和 BB，你需要對 AA 中的每一個點向 BB 中的每一個點都建一條邊，如果直接操作，複雜度很明顯是 O(n2)O(n2) 的，有沒有更快的方法呢？
我們可以建一個虛點 PP ，然後對 AA 里的每一個點向 PP 連一條單向邊邊，然後對 PP 向 BB 中的每一個點建一條單向邊，這樣只需要 O(2n)O(2n) 的複雜度就可以完成了。
畫個圖理解一下。
(優化前)
(優化後)
例題 P1983 車站分級
虛點連邊只是聽起來很高大上的操作，但實際上很簡單。
對於有邊權的情況，虛點連得邊的邊權需要注意(一般為 00 )
線段樹優化建邊
說到優化建邊，就一定要介紹一下線段樹優化建邊了。
這也是一個聽起來非常高大上但實際上不是很難的技巧。
給你一個點 XX ，讓你和一個點集裡的每一個點都連一條邊。看起來並沒有什麼好方法，只能乖乖地一個一個連
如果這個點集是連續的呢？我們就可以用線段樹來優化建邊了。
我們知道線段樹是這個結構的
我們知道，線段樹的點是能夠代表一段區間的，那麼我們怎樣應用這個性質呢？
首先，我們需要對於線段樹的每個父親與他的兒子建一條單向邊，效果如下
這有什麼用呢？因為我們所要求的點集是一段連續的區間，而線段樹的結點可以表示某一段區間，我們可以在線段樹上找到對應的區間，然後向線段樹上的點建邊，就可以加快建邊速度了。
例如我們要向 [1,8][1,8] 里的所有點建邊，我們只需要將 XX 和線段樹上 [1,8][1,8] 那個點連一條單向邊就可以了。
[2,6][2,6] 的例子
我們在線段樹上的邊邊權一般都是 00 ，邊權直接賦給 XX 連到線段樹上的那條邊即可
建樹和尋找的代碼和普通線段樹差不多。需要注意的是線段樹上結點的編號不要和已有的點重複，最後的結點直接連上該點就好。
CodesCodes
例題 CF786B Legacy
這道題還涉及到了區間向某一個點連邊的情況，我們再建一個棵線段樹在樹上反向建邊就可以了
拆點構圖
有些時候我們並不能用一個點來代表一個點（霧）
誒我不是這個意思。我的意思是用幾個點來表示一個點的不同情況。
隨機口胡的一道題
一個圖，每條邊上有 kk 個權值，第 ii 次行走消耗的代價是第 i%k+1i%k+1 個權值，求某一個點的單源最短路徑。 (k(k很小))
看起來直接跑 dijdij 和 spfaspfa 是不對的，可以自舉反例。
可以使用 dfsdfs ，用 dis[i][j]dis[i][j] 表示到第 ii 個點走了 mm 步且 m%k+1=jm%k+1=j 的最短方案，但這樣太慢了。
我們可以使用拆點的思想，對於一個點 ii ，將它拆為 i,i+n,i+2∗n,...i,i+n,i+2∗n,... 這樣的 kk 個點，作為到這個點的步數模 kk 不同情況的替代點。
然後我們連邊的時候對某一種情況賦不同情況的權值，大概下面這樣？
//我們要對 x 到 y 連三種邊 w1 w2 w3
add(x,y+n,w1);
add(x+n,y+2*n,w2);
add(x+2*n,y,w3);
來一張圖
然後在得到的圖上跑最短路就可以了，答案要枚舉到終點的情況。
類似的例題 P4568 飛行路線
圖論建模
似乎……一些背包問題可以用最短路解決，只是沒什麼必要。
LetusACit−−LetusACit−−題面
KodakKodak開了一家小店賺外快，因為店小，所以只有 nn 種不同價格的商品賣，不過好在批發商給力，貨源充足，所以每種商品都有無限件。
因為各種原因，有時候顧客會對購買的總價有特殊的要求，比如計算機科學家泰瑪仕一定要總價 10241024 ，給小姐姐買禮物的麵包需要總價 520520 或者 13141314 ，或者純粹來找茬的張三要買00元商品
但是KodakKodak店裡不一定有 11 元的商品，所以並不是所有價格都湊得出來，所以他需要一個程序解決能知道某一個總價能否湊出
看起來可以用完全背包解決這個問題，但是這道題的數據範圍不太友好。
商品數 N<=1000N<=1000 \ 商品價格 ai<=20000ai<=20000
顧客數 M<=300000M<=300000 \ 需求價格 bi<=40000000bi<=40000000
如果打完全背包，複雜度會爆炸。TATTAT
其實這個問題就是 a1∗x1+a2∗x2+a3∗x3+...?=ka1∗x1+a2∗x2+a3∗x3+...?=k 的問題。我們考慮 「「同餘 ++ 最短路」」
依題意得，如果 kk 滿足要求，那麼 am∗kam∗k 必定也滿足條件。我們可以先給它填一堆 amam ，然後減去 pp 個 amam ，用剩下的 aiai 表示 p∗am+k%amp∗am+k%am 設當 b%am=ib%am=i時，需要的最小的 k×am+ik×am+i 為 dis[i]dis[i] ，剩下的即可用最短路的思想來更新，
跑最短路的過程基本如下
memset(dis,0x3f,sizeof(dis));
dis[0]=0;
q.push(0);
while(q.size()){
int x=q.top();
q.pop();
if(v[x]) continue;
v[x]=1;
for(int i=1;i<=n;i++){
int y=(x+a[i])%mod;
if(dis[y]>dis[x]+a[i]){
dis[y]=dis[x]+a[i];
q.push(y);
}
}
}
可能不是太好理解，結合樣例手推一下吧
又一道例題
給出 nn 個 長度為 mm 的 0101 串，讓你確定一個長度相同的 0101 串，該串和給出的串中不同的位數最多。
一道看起來跟圖論毫無關係的題，其實也可以當作圖論來做
我們可以建一個 2m2m 的圖，每個點都與和自身不同位數為 11 的點連一條長度為 11 的邊，然後跑 bfsbfs，得到最遠距離的那個點即為所求。
廣搜代碼
這有點類似於前面講的虛點連邊的那道題。
我講的可能比較菜，可以畫圖理解。
圖論中要注意的坑
簡單列述幾個小問題
1.1. 先看眼是有向圖還是無向圖，無向圖數組開兩倍。
2.2. 如果題目中沒有聲明無自環和重邊，需要注意
3.3. 有些遍歷的題要考慮環，否則可能死循環，可以使用縮點
4.4. 如果題目中邊權小於等於零，要考慮負環、零環的情況
5.5. 跑最短路的時候要賦初值。
6.6. 關於 SpfaSpfa ，能不用還是不用吧，畢竟容易被卡。
文章來自https://www.cnblogs.com/sqrthyy/p/16526099.html