所謂拓?fù)渑判?，就是把AOV網(wǎng)中的所有活動(dòng)排成一個(gè)序列， 使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，這個(gè)過(guò)程稱為“拓?fù)渑判颉保玫降幕顒?dòng)序列稱為“拓?fù)湫蛄小薄?/p>

即把有向圖上的n個(gè)點(diǎn)重新標(biāo)號(hào)為1到n，滿足對(duì)于任意一條邊 (u, v)，都有u<v。

并不是所有的圖都能進(jìn)行拓?fù)渑判?，只要圖中有環(huán)，那么就可以導(dǎo)出矛盾。

因此拓?fù)渑判蛩惴ㄖ贿m用于AOV網(wǎng)（有向無(wú)環(huán)圖，DAG）,有向無(wú)環(huán)圖有很多優(yōu)美的性質(zhì)，比如可以在拓?fù)湫蛏线M(jìn)行DP。

一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁灰欢ㄊ俏ㄒ坏摹?/p>

實(shí)現(xiàn)

我們記錄一下每一個(gè)點(diǎn)的入度和出度，用一個(gè)隊(duì)列維護(hù)當(dāng)前所有入度為0的點(diǎn)。每次拿出來(lái)一個(gè)入度為0的點(diǎn)并且將它加到拓?fù)湫蛑校缓竺杜e出邊更新度數(shù)上述兩步，重復(fù)，直到不存在入度為0的頂點(diǎn)為止。

若完成時(shí)隊(duì)列中的頂點(diǎn)數(shù)小于AOV網(wǎng)中的頂點(diǎn)數(shù)，則圖中有回路，否則此隊(duì)列中的頂點(diǎn)序列就是一種拓?fù)湫颉?/p>

可以看出，拓?fù)渑判蚩梢杂脕?lái)判斷一個(gè)有向圖是否有環(huán)，因?yàn)橹挥杏邢驘o(wú)環(huán)圖才存在拓?fù)湫蛄小?/p>

時(shí)間復(fù)雜度O(n+m)。

（在拓?fù)渑判虻倪^(guò)程中可以順帶進(jìn)行DP）

思路

indgr[i]:頂點(diǎn)i的入度；

stack[ ]:棧；

初始化:top=0 (棧頂指針置零)；

將初始狀態(tài)所有入度為0的頂點(diǎn)壓棧；

I=0 (計(jì)數(shù)器)；

while 棧非空(top>0)

棧頂?shù)捻旤c(diǎn)v出棧；top-1; 輸出v；i++；

for v的每一個(gè)后繼頂點(diǎn)u

ndgr[u]--;//u的入度減1

if （u的入度變?yōu)?） 頂點(diǎn)u入棧

算法結(jié)束

代碼

	for(int i=1;i<=n;i++)
		if(d[i]==0)q.push(i);
	while(!q.empty()){
		int node=q.front();
		q.pop();
		res[++top]=node;
		for(int hd=head[node];hd;hd=e[hd].nxt){
			d[e[hd].to]--;
			if(d[e[hd].to]==0)
			q.push(e[hd].to);
		}
	}

歐拉路徑（歐拉通路）

如果圖中的一個(gè)路徑包括每個(gè)邊恰好一次，則該路徑稱為歐拉路徑。

歐拉回路

首尾相接的歐拉路徑稱為歐拉回路。

判定

由于每一條邊都要經(jīng)過(guò)恰好一次，因此對(duì)于除了起點(diǎn)和終點(diǎn)之外的任意一個(gè)節(jié)點(diǎn)，只要進(jìn)來(lái)，一定要出去。

一個(gè)無(wú)向圖存在歐拉回路，當(dāng)且僅當(dāng)該圖所有頂點(diǎn)度數(shù)都為偶數(shù)（即不存在奇點(diǎn)），且該圖只有一個(gè)存在邊的連通塊。

一個(gè)無(wú)向圖存在歐拉路徑，當(dāng)且僅當(dāng)該圖中奇點(diǎn)的數(shù)量為0或2，且該圖只有一個(gè)存在邊的連通塊；
如果存在2個(gè)奇點(diǎn)，則此歐拉路徑一定是從一個(gè)奇點(diǎn)出發(fā)，在另一個(gè)奇點(diǎn)結(jié)束。

一個(gè)有向圖存在歐拉回路，當(dāng)且僅當(dāng)所有點(diǎn)的入度等于出度。

一個(gè)混合圖存在歐拉回路，當(dāng)且僅當(dāng)存在一個(gè)對(duì)所有無(wú)向邊定向的方案，使得所有點(diǎn)的入度等于出度。需要用網(wǎng)絡(luò)流。

求法

我們用 dfs來(lái)求出一張圖的歐拉回路。

我們給每一條邊一個(gè) vis數(shù)組代表是否訪問(wèn)過(guò)，接下來(lái)從一個(gè)點(diǎn)出發(fā)，遍歷所有的邊。

直接dfs并且記錄的話會(huì)有一些問(wèn)題。

為了解決這個(gè)問(wèn)題，我們?cè)谟涗洿鸢傅臅r(shí)候倒著記錄，也就是當(dāng)我們通過(guò) (u, v) 這條邊到達(dá) v 的時(shí)候，先把 v dfs 完再加入 (v, u) 這條邊。

還有一點(diǎn)需要注意。因?yàn)橐粋€(gè)點(diǎn)可能被訪問(wèn)多次，一不小心可能會(huì)寫(xiě)成 O(n 2 ) 的（因?yàn)槊看伪闅v所有的出邊）。解決方案就是設(shè)一個(gè)cur數(shù)組，每次直接從上一次訪問(wèn)到的出邊繼續(xù)遍歷。

時(shí)間復(fù)雜度 O(n + m)。

代碼

	void dfs(int x)
	{
		for(int&hd=head[x];hd;hd=e[hd].nxt)
		{
			if(flag[hd>>1])continue;
			flag[hd>>1]=1;
			dfs(e[hd].to);
			a[++top]=x;
		}
	}

歐拉圖

有歐拉回路的圖稱為歐拉圖（Euler Graph）；

有歐拉通路而沒(méi)有歐拉回路的圖稱為半歐拉圖。

哈密爾頓通路

通過(guò)圖中每個(gè)頂點(diǎn)一次且僅一次的通路。

哈密爾頓回路

通過(guò)圖中每個(gè)頂點(diǎn)一次且僅一次的回路。

求法

一般用搜索解決。

哈密爾頓圖

存在哈密爾頓回路的圖。

最短路徑

所謂最短路，就是把邊權(quán)看做邊的長(zhǎng)度，從某個(gè)點(diǎn) S到另一個(gè)點(diǎn) T 的最短路徑。

用更加數(shù)學(xué)化的語(yǔ)言描述就是，對(duì)于映射 $ f : V \to R $ ,滿足 $ f \left ( S \right ) = 0 $ 且 $ \forall ( x , y , l ) \in E $ , | f ( x ) ? f ( y ) | $ \le l $ 的情況下，f(T) 的最大值。

最短路問(wèn)題

最短路問(wèn)題（short-path problem）是網(wǎng)絡(luò)理論解決的典型問(wèn)題之一，可用來(lái)解決管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等實(shí)際問(wèn)題。

基本內(nèi)容是：若網(wǎng)絡(luò)中的每條邊都有一個(gè)數(shù)值（長(zhǎng)度、成本、時(shí)間等），則找出兩節(jié)點(diǎn)（通常是源節(jié)點(diǎn)和終節(jié)點(diǎn)）之間總權(quán)和最小的路徑，也就是最短路問(wèn)題。

一般有兩類(lèi)最短路徑問(wèn)題：一類(lèi)是求從某個(gè)頂點(diǎn)（源點(diǎn)）到其它頂點(diǎn)（終點(diǎn)）的最短路徑,（Dijkstra、Bellman-ford、SPFA）；另一類(lèi)是求圖中每一對(duì)頂點(diǎn)間的最短路徑,（floyed）。

單源最短路——Dijkstra

在所有的邊權(quán)均為正的情況下，我們可以使用Dijkstra算法求出一個(gè)點(diǎn)到所有其它點(diǎn)的最短路徑。

我們維護(hù)一個(gè)集合，表示這個(gè)集合內(nèi)的點(diǎn)最短路徑已經(jīng)確定了。

每次我們從剩下的點(diǎn)中選擇當(dāng)前距離最小的點(diǎn) u 加入這個(gè)集合，然后枚舉另一個(gè)點(diǎn) v 進(jìn)行更新：

$ Dv = min \left ( Dv , Du + W \left ( u , v \right ) \right ) $

直接這樣做時(shí)間復(fù)雜度是 $ O \left ( n^2 \right ) $ 的。

實(shí)現(xiàn)

設(shè)起點(diǎn)為s，dis[ v ]表示從s到v的最短路徑，path[ v ]為v的前驅(qū)節(jié)點(diǎn)，用來(lái)輸出路徑。

1、初始化：

$ dis \left [ v \right ] = + \infty \left ( v \ne s \right ) ; $

$ dis \left [ s \right ] = 0 ; $

$ path \left [ s \right ] = 0 ; $

2、在沒(méi)有被訪問(wèn)過(guò)的點(diǎn)中找一個(gè)頂點(diǎn)u使得dis[ u ]是最小的。

3、u標(biāo)記為已確定最短路徑。

4、for與u相連的每個(gè)未確定最短路徑的頂點(diǎn)v。

#include<iostream>	
#include<cstring>   
using namespace std;   
const int inf=; 
const int maxn=101;
int f[maxn],a[maxn][maxn],d[maxn],path[maxn];  
int n,start; 
void init(){
	cin>>n>>m>>start;
	int x,y,w;
	for(int i=1;i<=n;i++)
	  	for(int j=1;j<=n;j++){
	  		if(j==i) a[i][j]=0;
	  		else a[i][j]=inf;
	  	}
	for(int i=1;i<=m;i++){        
		cin>>x>>y>>w;
		a[x][y]=w;
		a[y][x]=w;
	}
}
void dijkstra(int s){
	for(int i=1;i<=n;i++){
		d[i]=inf; 
		f[i]=false;  
	}
    d[s]=0;
    for(int i=1;i<=n;i++){
		int mind=inf;  
		int k;//用來(lái)記錄準(zhǔn)備放入集合1的點(diǎn)
		for(int j=1;j<=n;j++)//查找集合2中d[]最小的點(diǎn)
		if((!f[j])&&(d[j]<mind)){ 
			mind=d[j]; 
			k=j; 
		}
		if(mind==inf)break;//更新結(jié)點(diǎn)求完了
		f[k]=true;//加入集合1
		for(int j=1;j<=n;j++)//修改集合2中的d[j]
			if((!f[j])&&(d[k]+a[k][j]<d[j])){ 
				d[j]=d[k]+a[k][j];
				path[j]=k;
			}
    } 
}
void dfs(int i){
	if(i!=start)dfs(path[i]);
	cout<<i<<' ';
}
void write(){
    cout<<start<<"到其余各點(diǎn)的最短距離是："<<endl; 
    for(int i=1;i<=n;i++){
		if(i!=start){
	    	if(d[i]==inf)cout<<i<<"不可達(dá)";
	    	else{
				cout<<i<<"的最短距離："<<d[i]<<",依次經(jīng)過(guò)的點(diǎn)是：";
				dfs(path[i]);
				cout<<i<<endl;		 
	        } 
	    }		
    }
}
int main(){
	init();
	dijkstra(start);
	write();
	return 0; 
}

優(yōu)化

我們注意到，復(fù)雜度主要來(lái)源于兩個(gè)地方。

第一個(gè)是找出當(dāng)前距離最小的點(diǎn)。這個(gè)可以用堆很容易地實(shí)現(xiàn)。

第二個(gè)是枚舉 v，如果我們用鄰接表存圖，可以降到邊數(shù)級(jí)別。

這樣我們就把復(fù)雜度降到了 O((n + m) log n)。

單源最短路——Bellman-Ford

簡(jiǎn)稱Ford（福特）算法，另一種求單源最短路的算法，復(fù)雜度不如Dijkstra優(yōu)秀，能夠處理存在負(fù)邊權(quán)的情況，但無(wú)法處理存在負(fù)權(quán)回路的情況。

負(fù)權(quán)回路

存在負(fù)權(quán)回路的圖無(wú)法求出最短路徑，Bellman-Ford算法可以在有負(fù)權(quán)回路的情況下輸出錯(cuò)誤提示。

如果在Bellman-Ford算法的兩重循環(huán)完成后，還是存在某條邊使得： $ dis \left [ u \right ] + w \left [ j \right ] < dis \left [ v \right ] $ ，則存在負(fù)權(quán)回路。

if(dis[u]+w[j]<dis[v])return false;

實(shí)現(xiàn)

設(shè)s為起點(diǎn)，dis[ v ]即為s到v的最短距離，pre[v]為v前驅(qū)。w[ j ]是邊j的長(zhǎng)度，且j連接u、v。

初始化：

$ dis \left [ v \right ] = + \infty \left ( v \ne s \right ) ; $

$ dis \left [ s \right ] = 0 ; $

$ path \left [ s \right ] = 0 ; $

考慮在上面出現(xiàn)過(guò)的松弛操作：

dv = min(dv, du + w(u, v))

由于最短路徑只會(huì)經(jīng)過(guò)最多 n 個(gè)點(diǎn)，因此每一個(gè)點(diǎn)的最短路徑只會(huì)被松弛至多 n ? 1 次。

所以我們可以對(duì)整張圖進(jìn)行 n ? 1 次松弛操作，每次枚舉所有的邊進(jìn)行更新。

for(i=1;i<=n-1;i++)
	for(j=1;j<=E;j++)//枚舉所有邊，而不是枚舉點(diǎn)
		if(dis[u]+w[j]<dis[v]){//u、v分別是這條邊連接的兩個(gè)點(diǎn)。
     	  	dis[v] =dis[u] + w[j];
       		pre[v] = u;
  		}

時(shí)間復(fù)雜度 O(nm)。

SPFA

它死了。（因?yàn)樗膹?fù)雜度是錯(cuò)誤的）

應(yīng)用：費(fèi)用流

Bellman-Ford算法不夠優(yōu)秀，于是我們嘗試改進(jìn)這個(gè)算法。

注意到，在進(jìn)行松弛操作的時(shí)候，如果點(diǎn) u 的距離一直沒(méi)有發(fā)生變化，那么就不需要再枚舉這個(gè)點(diǎn)的出邊進(jìn)行松弛了。

也就是說(shuō)我們可以用一個(gè)隊(duì)列保存所有距離發(fā)生變化的點(diǎn)， 每次取出一個(gè)點(diǎn)進(jìn)行更新。

（主要思想：初始時(shí)將起點(diǎn)加入隊(duì)列。每次從隊(duì)列中取出一個(gè)元素，并對(duì)所有與它相鄰的點(diǎn)進(jìn)行修改，若某個(gè)相鄰的點(diǎn)修改成功，則將其入隊(duì)。直到隊(duì)列為空時(shí)算法結(jié)束。）

于是SPFA就誕生了。

如果圖是隨機(jī)的，SPFA的期望時(shí)間復(fù)雜度約為 O(2m)，比之前提到的任何一個(gè)算法都優(yōu)秀，而且還可以有負(fù)權(quán)。

但是在最壞情況下它的復(fù)雜度和 Bellman-Ford 相同，都是 O(nm)，在正式比賽中，沒(méi)有哪個(gè)出題人會(huì)放過(guò)它。（因?yàn)槠鋸?fù)雜度本來(lái)就是錯(cuò)的）

多源最短路——Floyed

對(duì)于一張圖，我們希望求出任意兩個(gè)點(diǎn)之間的最短路徑。

我們用 DP（動(dòng)態(tài)規(guī)劃） 的思想。設(shè) fi,j,k 表示從 i 到 j，途中僅經(jīng)過(guò)前 k個(gè)點(diǎn)的最短路。

由于每一個(gè)點(diǎn)在最短路中只會(huì)出現(xiàn)一次（不然就出現(xiàn)負(fù)環(huán)了，不存在最短路），所以可以很寫(xiě)出轉(zhuǎn)移方程：

fi,j,k = min(fi,j,k?1, fi,k,k?1 + fk,j,k?1)

時(shí)間復(fù)雜度是 $ O \left ( n^3 \right ) $ 。

在實(shí)際求的過(guò)程中，最后一維可以用滾動(dòng)數(shù)組優(yōu)化掉，所以空間復(fù)雜度是 $ O \left ( n^2 \right ) $ 。

代碼

for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

注意三層循環(huán)的順序不能顛倒。

初始化

$ d \left [ i \right ] \left [ i \right ] = 0 $ //自己到自己為0；

$ d \left [ i \right ] \left [ i \right ] = 邊權(quán) $ //i與j有直接相連的邊；

$ d \left [ i \right ] \left [ i \right ] = + \infty $ //i與j無(wú)直接相連的邊。

// 如果是int數(shù)組，采用memset(d, 0x7f, sizeof(d))可全部初始化為一個(gè)很大的數(shù)

Floyd 傳遞閉包

有時(shí)候，我們需要維護(hù)一些有傳遞性的關(guān)系，比如相等，連通等等。（12連通，23連通，則 13連通）

初始條件往往是已知若干個(gè)點(diǎn)對(duì)具有這些關(guān)系，然后讓你弄 出來(lái)所有的關(guān)系。

可以直接把 Floyd 算法做一下調(diào)整——

dis[i][j]=dis[i][j]|(dis[i][k]&dis[k][j]);

這個(gè)算法叫做傳遞閉包。

多源最短路——Johnson 重賦權(quán)

對(duì)于多源最短路，如果我們枚舉一個(gè)點(diǎn)然后跑堆優(yōu)化的 Dijkstra，那么復(fù)雜度是 O(nm log n) 的，在圖比較稀疏的情況下，這個(gè)復(fù)雜度要優(yōu)于 Floyd 算法的 O(n 3 )。

但是 Dijkstra 算法要求所有邊權(quán)均非負(fù)。

于是就有了重賦權(quán)的技巧。

我們新建一個(gè) 0 號(hào)點(diǎn)，并且從這個(gè)點(diǎn)出發(fā)向所有點(diǎn)連一條邊 權(quán)為 0 的邊，然后跑單源最短路。（SPFA 或者 Bellman-Ford）

設(shè)距離數(shù)組為 h，接下來(lái)對(duì)于每條邊 (u, v)，令 w ′ (u, v) = w(u, v) + h(u) ? h(v)。

這樣所有的邊權(quán)就都變成非負(fù)了，我們就可以跑 Dijkstra 算法了。

證明

首先由于 h(v) ≤ h(u) + w(u, v)，新圖的邊權(quán)一定非負(fù)。

設(shè)新圖上的最短路徑為 d ′，原圖上的最短路徑為 d。

d ′ (u, v) = min a1,a2,...,ak w ′ (u, a1) + w ′ (a1, a2) + · · · + w ′ (ak, v)

= min a1,a2,...,ak w(u, a1) + (h(u) ? h(a1)) + w(a1, a2)+ (h(a2) ? h(a1)) + · · · + w(ak, v) + (h(v) ? h(ak))

= h(u) ? h(v) + min a1,a2,...,ak w(u, a1) + · · · + w(ak, v)

= h(u) ? h(v) + d(u, v)

最短路樹(shù)（最短路圖）

所謂最短路樹(shù)，就是在求完從 S 出發(fā)的單源最短路之后，

只保留最短路上的邊形成的數(shù)據(jù)結(jié)構(gòu)。

只需要在求的過(guò)程中維護(hù)一個(gè)pre數(shù)組表示這個(gè)點(diǎn)的前驅(qū)即可。很多最短路的變種都需要用這個(gè)算法。

最小生成樹(shù)

用來(lái)解決如何用最小的代價(jià)用N-1條邊連接N個(gè)點(diǎn)的問(wèn)題。

Prim 算法

類(lèi)比 Dijkstra 算法，我們維護(hù)一個(gè)集合 S，表示這個(gè)集合中 的生成樹(shù)已經(jīng)確定了。

算法流程和Dijkstra一樣，唯一的區(qū)別是用w(u, v) 去更新 dv 而不是用 du + w(u, v)。

時(shí)間復(fù)雜度 $ O \left ( n^2 \right ) $ ，同樣可以用堆優(yōu)化。

主要思想

Prim算法采用“藍(lán)白點(diǎn)”思想：白點(diǎn)代表已經(jīng)進(jìn)入最小生成樹(shù)的點(diǎn)，藍(lán)點(diǎn)代表未進(jìn)入最小生成樹(shù)的點(diǎn)。

Prim算法每次循環(huán)都將一個(gè)藍(lán)點(diǎn)u變?yōu)榘c(diǎn)，并且此藍(lán)點(diǎn)u與白點(diǎn)相連的最小邊權(quán)min[u]還是當(dāng)前所有藍(lán)點(diǎn)中最小的。

這樣相當(dāng)于向生成樹(shù)中添加了n-1次最小的邊，最后得到的一定是最小生成樹(shù)。

n次循環(huán)，每次循環(huán)讓一個(gè)新的點(diǎn)加入生成樹(shù)，n次循環(huán)就能把所有點(diǎn)囊括到其中；每次循環(huán)我們都能讓一條新的邊加入生成樹(shù)，n-1次循環(huán)就能生成一棵含有n個(gè)點(diǎn)的樹(shù)；每次循環(huán)我們都取一條最小的邊加入生成樹(shù)，n-1次循環(huán)結(jié)束后，我們得到的就是一棵最小的生成樹(shù)。

實(shí)現(xiàn)

以第一個(gè)點(diǎn)為起點(diǎn)生成最小生成樹(shù)，min[ v ]表示藍(lán)點(diǎn)v與白點(diǎn)相連的最小邊權(quán)。

MST表示最小生成樹(shù)的權(quán)值之和。

初始化：

$ min \left [ v \right ] = + \infty \left ( v \ne 1 \right ) ; $

$ min \left [ 1 \right ] = 0 ; $

$ MST = 0 ; $

部分偽代碼：

for (i = 1; i<= n; i++)
	尋找min[u]最小的藍(lán)點(diǎn)u。
	將u標(biāo)記為白點(diǎn)
	MST+=min[u]
	for 與白點(diǎn)u相連的所有藍(lán)點(diǎn)v  
   		if (w[u][v]<min[v]) 
   		min[v]=w[u][v];

算法結(jié)束：

MST即為最小生成樹(shù)的權(quán)值之和

Kruskal 算法

前置知識(shí)

并查集算法

并查集主要用于解決一些元素分組的問(wèn)題。它管理一系列不相交的集合，并支持兩種操作：

合并：把兩個(gè)不相交的集合合并為一個(gè)集合。

查詢：查詢兩個(gè)元素是否在同一個(gè)集合中。

主要思想

Kruskal算法將一個(gè)連通塊當(dāng)做一個(gè)集合。

Kruskal首先將所有的邊按從小到大順序排序（快排），并認(rèn)為每一個(gè)點(diǎn)都是孤立的，分屬于n個(gè)獨(dú)立的集合。

然后按順序枚舉每一條邊。如果這條邊連接著兩個(gè)不同的集合，那么就把這條邊加入最小生成樹(shù)，這兩個(gè)不同的集合就合并成了一個(gè)集合；如果這條邊連接的兩個(gè)點(diǎn)屬于同一集合，就跳過(guò)。

直到選取到第n-1條邊為止。

因?yàn)槭乔蟮淖钚∩蓸?shù)，所以我們用貪心的思路，把所有的邊權(quán)從小到大排序，然后一條一條嘗試加入，用并查集維護(hù)連通性。

可以發(fā)現(xiàn)這樣一定能得到原圖的最小生成樹(shù)。

時(shí)間復(fù)雜度$ O \left ( m log m \right ) $ 。

實(shí)現(xiàn)

初始化并查集：

$ father \left [ x \right ] = x $

$ tot = 0 $

將所有邊用快排從小到大排序。

計(jì)數(shù)器 k=0;

for(i=1;i<=M;i++)//遍歷所有邊 
  	if(這是一條u,v不屬于同一集合的邊(u,v)(因?yàn)橐呀?jīng)排序，所以必為最小)){
		合并u,v所在的集合
		把邊(u,v)加入最小生成樹(shù)
　    	tot=tot+W(u,v);
    	k++;
      	if(k=n-1)//說(shuō)明最小生成樹(shù)已經(jīng)生成
			break; 
	} 

結(jié)束，tot即為最小生成樹(shù)的總權(quán)值之和。

代碼

find(int x){
	return x==pa[x]?x:pa[x]=find(pa[x])
}

證明

如果某一條邊 (u, v) 不屬于最小生成樹(shù)，那么考慮最小生成樹(shù)上 連接 u, v 的路徑，這上面一定有一條邊權(quán)不小于 w(u, v) 的邊 （因?yàn)槲覀兪菑男〉酱竺杜e的所有邊），這樣替換后答案一定不會(huì)變劣。

優(yōu)化

路徑壓縮（O(logn)）+安值合并（O(logn)）→O(αn)（αn在 $ 10^8 $ 數(shù)據(jù)內(nèi)不超過(guò)4，可視為常數(shù)）

Kruskal 重構(gòu)樹(shù)

前置知識(shí)

dfs（深度優(yōu)先搜索）

LCA（最近公共祖先）

在一棵沒(méi)有環(huán)的樹(shù)上，每個(gè)節(jié)點(diǎn)肯定有其父親節(jié)點(diǎn)和祖先節(jié)點(diǎn)，而最近公共祖先，就是兩個(gè)節(jié)點(diǎn)在這棵樹(shù)上深度最大的公共的祖先節(jié)點(diǎn)。

LCA主要是用來(lái)處理當(dāng)兩個(gè)點(diǎn)僅有唯一一條確定的最短路徑時(shí)的路徑。

樹(shù)上倍增

用于求LCA（最近公共祖先）。

倍增的思想是二進(jìn)制。

首先開(kāi)一個(gè)n×logn的數(shù)組，比如fa[n][logn],其中fa[i][j]表示i節(jié)點(diǎn)的第2^j個(gè)父親是誰(shuí)。

然后，我們會(huì)發(fā)現(xiàn)一個(gè)性質(zhì)：

fa[i][j]=fa[fa[i][j-1]][j-1]

用文字?jǐn)⑹鰹椋篿的第2^j個(gè)父親 是i的第2^{(j-1)個(gè)父親的第2}(j-1)個(gè)父親。

這樣，本來(lái)我們求i的第k個(gè)父親的復(fù)雜度是O(k)，現(xiàn)在復(fù)雜度變成了O(logk)。

Kruskal 重構(gòu)樹(shù)是基于 Kruskal 最小生成樹(shù)算法的一種算 法，它主要通過(guò)將邊權(quán)轉(zhuǎn)化為點(diǎn)權(quán)來(lái)實(shí)現(xiàn)。

流程

將所有邊按照邊權(quán)排序，設(shè) r(x) 表示 x 所在連通塊的根節(jié)點(diǎn)。（注意這里要用并查集）

枚舉所有的邊 (u, v)，若 u, v 不連通，則新建一個(gè)點(diǎn) x，令 x 的權(quán)值為 w(u, v)。 連接 (x, r(u)) 和 (x, r(v))。 令 r(u) = r(v) = x。

不斷重復(fù)以上過(guò)程，直到所有點(diǎn)均連通。

時(shí)間復(fù)雜度 O(m log m)。

性質(zhì)

這樣，我們就得到了一棵有 2n ? 1 個(gè)節(jié)點(diǎn)的二叉樹(shù)，其中葉節(jié)點(diǎn)為原圖中的點(diǎn)，其余的點(diǎn)代表原圖中的邊，并且滿足父節(jié)點(diǎn)權(quán)值大于等于子節(jié)點(diǎn)。

它有什么用呢？

求 u, v 之間路徑上的最大邊權(quán) → 求重構(gòu)樹(shù)上 u, v 兩個(gè)點(diǎn)的 LCA。

只保留邊權(quán)小于等于 x 的邊形成的樹(shù) → 重構(gòu)樹(shù)上點(diǎn)權(quán)小于 等于 x 的點(diǎn)的子樹(shù)。

Bor?vka 算法

前置知識(shí)

距離

（x1,y1）（x2,y2）

曼哈頓距離：|x1-x2|+|y1-y2|

切比雪夫距離：max(|x1-x2|,|y1-y2|

歐幾里得距離：√[(x1-x2)2+(y1-y2)2]

曼哈頓距離與切比雪夫距離的相互轉(zhuǎn)化

兩者之間的關(guān)系

我們考慮最簡(jiǎn)單的情況，在一個(gè)二維坐標(biāo)系中，設(shè)原點(diǎn)為(0,0)。

如果用曼哈頓距離表示，則與原點(diǎn)距離為1的點(diǎn)會(huì)構(gòu)成一個(gè)邊長(zhǎng)為2–√2的正方形。

如果用切比雪夫距離表示，則與原點(diǎn)距離為1的點(diǎn)會(huì)構(gòu)成一個(gè)邊長(zhǎng)為2的正方形。

對(duì)比這兩個(gè)圖形，我們會(huì)發(fā)現(xiàn)這兩個(gè)圖形長(zhǎng)得差不多，他們應(yīng)該可以通過(guò)某種變換互相轉(zhuǎn)化。

事實(shí)上,

將一個(gè)點(diǎn)(x,y)的坐標(biāo)變?yōu)?x+y,x?y)后,原坐標(biāo)系中的曼哈頓距離=新坐標(biāo)系中的切比雪夫距離。

將一個(gè)點(diǎn)(x,y)的坐標(biāo)變?yōu)?（x+y）/2,（x?y）/2)后,原坐標(biāo)系中的切比雪夫距離=新坐標(biāo)系中的曼哈頓距離。

（注意：切比雪夫距離轉(zhuǎn)曼哈頓距離要再除以二）

用處

切比雪夫距離在計(jì)算的時(shí)候需要取max，往往不是很好優(yōu)化，對(duì)于一個(gè)點(diǎn)，計(jì)算其他點(diǎn)到該的距離的復(fù)雜度為O(n)。

而曼哈頓距離只有求和以及取絕對(duì)值兩種運(yùn)算，我們把坐標(biāo)排序后可以去掉絕對(duì)值的影響，進(jìn)而用前綴和優(yōu)化，可以把復(fù)雜度降為O(1)。

第三種求最小生成樹(shù)的算法，雖然比較冷門(mén)但是很多題需要用到這個(gè)算法。

我們維護(hù)當(dāng)前形成的所有連通塊，接下來(lái)對(duì)于每一個(gè)連通塊，找到邊權(quán)最小的出邊，然后合并兩個(gè)連通塊。

不斷重復(fù)這個(gè)操作，直到整張圖變成一個(gè)連通塊。

由于每次操作連通塊數(shù)量至少減半，所以時(shí)間復(fù)雜度最壞為 O((n + m) log n)，隨機(jī)圖的話復(fù)雜度可以降到 O(n + m)。

Tarjan算法

Tarjan 算法不是某個(gè)特定的算法，而是一群算法。

強(qiáng)連通分量

割點(diǎn)/割邊/橋

點(diǎn)雙連通分量

邊雙連通分量

離線 O(n) 求 LCA

此外還有很多 Tarjan 獨(dú)立/合作創(chuàng)造的算法：

Splay，LCT， 斐波那契堆，斜堆，配對(duì)堆，可持久化數(shù)據(jù)結(jié)構(gòu)，……

有向圖——強(qiáng)連通分量

如果對(duì)于兩個(gè)點(diǎn) u, v，同時(shí)存在從 u 到 v 的一條路徑和從 v 到 u 的一條路徑，那么就稱這兩個(gè)點(diǎn)強(qiáng)連通。

如果一張圖的任意兩個(gè)點(diǎn)均強(qiáng)連通，那么就稱這張圖為強(qiáng)連通圖。

強(qiáng)連通分量指的是一張有向圖的極大強(qiáng)連通子圖。 （極大≠最大）

Tarjan 算法可以用來(lái)找出一張有向圖的所有強(qiáng)連通分量。

我們用 dfs的方式來(lái)找出一張圖的強(qiáng)連通分量。

建出 dfs 樹(shù)，記錄一下每一個(gè)節(jié)點(diǎn)的時(shí)間戳(dfn)，然后我們考慮強(qiáng)連通分量應(yīng)該滿足什么條件。

我們可以再記錄一個(gè) low 數(shù)組，表示每一個(gè)點(diǎn)能夠到達(dá)的最小的時(shí)間戳，如果一個(gè)點(diǎn)的 dfn=low，那么這個(gè)點(diǎn)下方就形成了一個(gè)強(qiáng)連通分量。

在 dfs 的過(guò)程中，對(duì)于 (u, v) 這條邊：

若 v 未被訪問(wèn)，則遞歸進(jìn)去 dfs 并且用 low[v] 更新 low[u]。

若 v 已經(jīng)被訪問(wèn)并且在棧中，則直接用 dfn[v] 更新 low[u]。

最后如果 dfn[u]=low[u]，則直接把棧中一直到 u 的所有點(diǎn) 拿出來(lái)作為一個(gè)強(qiáng)連通分量。

時(shí)間復(fù)雜度 O(n)。

有向圖——縮點(diǎn)

跑出來(lái)強(qiáng)連通分量之后，我們可以把一個(gè)強(qiáng)連通分量看成一 個(gè)點(diǎn)。

接下來(lái)枚舉所有的邊，如果是一個(gè)強(qiáng)連通分量里的就忽略， 否則連接兩個(gè)對(duì)應(yīng)的強(qiáng)連通分量。這個(gè)操作稱為縮點(diǎn)。

縮點(diǎn)后就變成了一張有向無(wú)環(huán)圖，處理連通性問(wèn)題的時(shí)候會(huì)方便很多。

無(wú)向圖——割點(diǎn)

對(duì)于一張無(wú)向圖，我們希望求出它的割點(diǎn)。

無(wú)向圖的割點(diǎn)定義為刪掉這個(gè)點(diǎn)之后，連通塊數(shù)量會(huì)發(fā)生改變的點(diǎn)。

類(lèi)比上面，我們還是記錄一下 dfn（時(shí)間戳）和 low。

對(duì)于 u 的一個(gè)子節(jié)點(diǎn) v，若 dfn[u]≤low[v]，則 u 是割點(diǎn)（因 為 v 無(wú)法繞過(guò) u 往上走）。

不過(guò)需要注意兩點(diǎn)：

根節(jié)點(diǎn)不能用這種方法，而是應(yīng)該看它的子節(jié)點(diǎn)數(shù)量是否大于等于 2，如果是那么根節(jié)點(diǎn)就是割點(diǎn)。

枚舉出邊的時(shí)候要特判掉父子邊的情況。

無(wú)向圖——橋

無(wú)向圖的橋定義為刪掉這條邊后，連通塊數(shù)量會(huì)發(fā)生改變的邊。

和上面的方法幾乎一模一樣，唯一的區(qū)別是判斷dfn[u]<low[v]而不是dfn[u]≤low[v]。（如果從 v 出發(fā)連 u 都無(wú)法 到達(dá)，那么 (u, v) 就是一個(gè)橋邊）

甚至連根節(jié)點(diǎn)都不需要特判了。

無(wú)向圖——點(diǎn)/邊雙連通分量

如果兩個(gè)點(diǎn)之間存在兩條點(diǎn)互不相交的路徑，那么就稱這兩個(gè)點(diǎn)是點(diǎn)雙連通的。

如果兩個(gè)點(diǎn)之間存在兩條邊互不相交的路徑，那么就稱這兩個(gè)點(diǎn)是邊雙連通的。

其余的定義參考強(qiáng)連通分量。

割點(diǎn)將整張圖分成了若干個(gè)點(diǎn)雙連通分量，并且一個(gè)割點(diǎn)可以在多個(gè)點(diǎn)雙連通分量中。

而橋則把整張圖拆成了若干個(gè)邊雙連通分量，并且橋不在任意一個(gè)邊雙連通分量中。

魔改一下強(qiáng)連通分量算法即可。

當(dāng)然，無(wú)向圖也可以縮點(diǎn)，不過(guò)主要還是可以用來(lái)建圓方樹(shù)。

二分圖匹配

前置知識(shí)

匹配

在圖論中，一個(gè)匹配是一個(gè)邊的集合， 其中任意兩條邊都沒(méi)有公共頂點(diǎn)。

最大匹配

一個(gè)圖所有匹配中，所含匹配邊數(shù)最多的匹配， 稱為這個(gè)圖的最大匹配。

如果要求一般圖的最大匹配，需要用 O(n3) 的帶花樹(shù)，至少 是 NOI+ 的算法。在聯(lián)賽階段，我們一般只關(guān)注二分圖的匹配問(wèn)題。

(最大匹配——匈牙利算法)

完美匹配

如果一個(gè)圖的某個(gè)匹配中，所有的頂點(diǎn)都是匹配點(diǎn)，那么它就是一個(gè)完美匹配。

二分圖

如果一個(gè)圖的頂點(diǎn)能夠被分為兩個(gè)集合 X, Y，滿 足每一個(gè)集合內(nèi)部都沒(méi)有邊相連，那么這張圖被稱作是一張二分圖。

（dfs可以判斷一張圖是否是二分圖）

交替路

從一個(gè)未匹配點(diǎn)出發(fā)，依次經(jīng)過(guò)非匹配邊——匹配 邊——非匹配邊——……形成的路徑叫交替路。

增廣路

從一個(gè)未匹配點(diǎn)出發(fā)，依次經(jīng)過(guò)非匹配邊——匹配 邊——非匹配邊——……——非匹配邊，最后到達(dá)一個(gè)未匹配點(diǎn)形成的路徑叫增廣路。

注意到，一旦我們找出了一條增廣路，將這條路徑上所有匹配邊和非匹配邊取反，就可以讓匹配數(shù)量+1。

匈牙利算法就是基于這個(gè)原理。

假設(shè)我們已經(jīng)得到了一個(gè)匹配，希望找到一個(gè)更大的匹配。

我們從一個(gè)未匹配點(diǎn)出發(fā)進(jìn)行 dfs（深度優(yōu)先搜索），如果找出了一個(gè)增廣路， 就代表增廣成功，我們找到了一個(gè)更大的匹配。

如果增廣失敗，可以證明此時(shí)就是最大匹配。

由于每個(gè)點(diǎn)只會(huì)被增廣一次，所以時(shí)間復(fù)雜度是 O(n(n + m))。

二分圖最大權(quán)匹配——KM 算法

現(xiàn)在我們把所有的邊都帶上權(quán)值，希望求出所有最大匹配中權(quán)值之和最大的匹配。

我們的思路是給每一個(gè)點(diǎn)賦一個(gè)“期望值”，也叫作頂標(biāo)函數(shù) c，對(duì)于 (u, v) 這條邊來(lái)說(shuō)，只有 c(u) + c(v) = w(u, v) 的時(shí) 候，才能被使用。

容易發(fā)現(xiàn)，此時(shí)的答案就是 ∑c(i)。

初始，我們令左邊所有點(diǎn)的 c(u) = maxv w(u, v)，也就是說(shuō)最理想的情況下，每一個(gè)點(diǎn)都被權(quán)值最大的出邊匹配。

接下來(lái)開(kāi)始增廣，每次只找符合要求的邊。我們定義只走這些邊訪問(wèn)到的子圖為相等子圖。

如果能夠找到增廣路就直接增廣，否則，就把這次增廣訪問(wèn)到的左邊的所有點(diǎn)的 c ? 1，右邊所有點(diǎn)的 c + 1。

經(jīng)過(guò)這樣一通操作，我們發(fā)現(xiàn)原來(lái)的匹配每一條邊仍然滿足條件。同時(shí)由于訪問(wèn)到的點(diǎn)左邊比右邊多一個(gè)（其余的都匹配上了），所以這樣會(huì)導(dǎo)致總的權(quán)值?1。

接下來(lái)再嘗試進(jìn)行增廣，重復(fù)上述過(guò)程。直接這樣做時(shí)間復(fù) 雜度是 O(n 3 c) 的。（進(jìn)行 n 次增廣，每次修改 c 次頂標(biāo)，訪問(wèn)所有 n 2 條邊）

優(yōu)化

由于修改頂標(biāo)的目標(biāo)是讓相等子圖變大，因此可以每次加減 一個(gè)最小差值 delta。這樣每次增廣只會(huì)被修改最多 n 次頂標(biāo)，時(shí)間復(fù)雜度降到 O(n 4 )。

注意到每次重新進(jìn)行 dfs（深度優(yōu)先搜索） 太不優(yōu)秀了，可以直接進(jìn)行 bfs， 每次修改完頂標(biāo)之后接著上一次做。時(shí)間復(fù)雜度降到 O(n 3 )。

技巧

最小點(diǎn)覆蓋

選取最少的點(diǎn)，使得每一條邊的兩端至少有一 個(gè)點(diǎn)被選中。

二分圖的最小點(diǎn)覆蓋 = 最大匹配

證明

1.由于最大匹配中的邊必須被覆蓋，因此匹配中的每一個(gè)點(diǎn)對(duì) 中都至少有一個(gè)被選中。

2.選中這些點(diǎn)后，如果還有邊沒(méi)有被覆蓋，則找到一條增廣路，矛盾。

最大獨(dú)立集：選取最多的點(diǎn)，使得任意兩個(gè)點(diǎn)不相鄰。

最大獨(dú)立集 = 點(diǎn)數(shù)-最小點(diǎn)覆蓋

證明

1.由于最小點(diǎn)覆蓋覆蓋了所有邊，因此選取剩余的點(diǎn)一定是一個(gè)合法的獨(dú)立集。

2.若存在更大的獨(dú)立集，則取補(bǔ)集后得到了一個(gè)更小的點(diǎn)覆蓋，矛盾。

最小邊覆蓋：選取最少的邊，使得每一個(gè)點(diǎn)都被覆蓋。

最小邊覆蓋 = 點(diǎn)數(shù)-最大匹配

證明

1.先選取所有的匹配邊，然后對(duì)剩下的每一個(gè)點(diǎn)都選擇一條和 它相連的邊，可以得到一個(gè)邊覆蓋。

2.若存在更小的邊覆蓋，則因?yàn)檫B通塊數(shù)量 = 點(diǎn)數(shù)-邊數(shù)，這 個(gè)邊覆蓋在原圖上形成了更多的連通塊，每一個(gè)連通塊內(nèi)選一條邊，我們就得到了一個(gè)更大的匹配。

最小不相交路徑覆蓋：一張有向圖，用最少的鏈覆蓋所有的點(diǎn)，鏈之間不能有公共點(diǎn)。

將點(diǎn)和邊分別作為二分圖的兩邊，然后跑匹配，最小鏈覆蓋 = 原圖點(diǎn)數(shù)-最大匹配。

最小可相交路徑覆蓋：一張有向圖，用最少的鏈覆蓋所有的 點(diǎn)，鏈之間可以有公共點(diǎn)。

先跑一遍傳遞閉包，然后變成最小不相交路徑覆蓋。

補(bǔ)充

小黃鴨調(diào)試法

當(dāng)你的代碼出現(xiàn)問(wèn)題的時(shí)候，

將小黃鴨想象成你的同學(xué)，

將你的代碼一行一行地講給它，

也許講到一半你就知道問(wèn)題出在哪了。

不要定義以下變量名

next,abs,x1,y1,size……

并非原創(chuàng)，僅是整理，請(qǐng)見(jiàn)諒

網(wǎng)站題目：圖論
分享地址：http://chinadenli.net/article34/dsoihse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、關(guān)鍵詞優(yōu)化、外貿(mào)建站、動(dòng)態(tài)網(wǎng)站、網(wǎng)站營(yíng)銷(xiāo)、全網(wǎng)營(yíng)銷(xiāo)推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)