It計(jì)算機(jī)課件 山東大學(xué)ACM模板-圖論

圖論

1

1.最短路徑..............................................................................4

1)Dijkstra之優(yōu)雅stl...............................................................4

2)Dijkstra_模擬數(shù)組..............................................................4

3)Dijkstra陣......................................................................5

4)SPFA優(yōu)化........................................................................6

5)差分約束系統(tǒng).....................................................................7

2.K短路................................................................................7

1)Readme............................................................................7

2)K短路一無(wú)環(huán)一Astar.................................................................7

3)K短路三環(huán)一Yen..................................................................10

4)K短路一無(wú)環(huán)一Yen_字典序..........................................................12

5)K短路一有環(huán)_Astar................................................................15

6)K短路一有環(huán).Yen..................................................................17

7)次短路經(jīng)&&曲徑數(shù)................................................................20

3.連通分支.............................................................................21

1)圖論一SCC........................................................................21

2)2-sat............................................................................23

3)BCC..............................................................................25

4.生成樹(shù)...............................................................................27

1)Kruskal..........................................................................27

2)Prim_MST是否唯一...............................................................28

3)Prim陣..........................................................................29

4)度限制MST.......................................................................30

5)次小生成樹(shù)......................................................................34

6)次小生成樹(shù)_陣..................................................................36

7)嚴(yán)格次小生成樹(shù)..................................................................37

8)K小生成樹(shù)偽代碼................................................................41

9)MST計(jì)數(shù)一連通性狀壓一N0I07.......................................................41

10)曼哈頓MST.......................................................................43

11)曼哈頓MST一基數(shù)排序............................................................46

12)生成樹(shù)變MST_sgu206.............................................................49

13)生成樹(shù)計(jì)數(shù).....................................................................52

14)最小生成樹(shù)計(jì)數(shù).................................................................53

15)最小樹(shù)形圖.....................................................................56

16)圖論—最小樹(shù)形圖_double_poj3壹64...............................................58

5.最大流...............................................................................60

1)EdmondsKarp算法...............................................................60

2)SAP鄰接矩陣....................................................................61

3)SAP模擬數(shù)組....................................................................62

4)SAP_BFS..........................................................................63

5)sgu壹85_AC(兩條最短路徑)......................................................64

6)有上下界的最大流一數(shù)組模擬.....................................................67

6.費(fèi)用流...............................................................................69

1)費(fèi)用流_SPFA_i^^................................................................69

2)費(fèi)用流_SPFA」肖圈................................................................70

3)ZKW數(shù)由模擬....................................................................72

7.割.................................................................................73

1)最大權(quán)閉合圖...................................................................73

2)最大密度子圖....................................................................73

3)二分圖的最小點(diǎn)權(quán)覆蓋...........................................................74

4)二分圖的最大點(diǎn)權(quán)獨(dú)立集.........................................................75

5)無(wú)向圖最小割_Stoer-Wagner算法.................................................75

6)無(wú)向圖最大割....................................................................76

7)無(wú)向圖最大割(壹6ms)............................................................76

8.二分圖...............................................................................78

1)二分圖最大匹配Edmonds..........................................................78

2)必須邊..........................................................................79

3)最小路徑覆蓋(路徑不相交).....................................................79

2

4)二分圖最大匹配HK..........................................................................................................................80

5)KM算法一樸素_0(n4)........................................................................................................................81

6)KM算法一slack_0(n3)......................................................................................................................82

7)點(diǎn)BCC_二分判出一(2942圓桌騎士).................................................84

8)二分圖多重匹配..................................................................86

9)二分圖判定......................................................................88

10)最小路徑覆蓋(帶權(quán))...........................................................89

9.一般圖匹配..........................................................................90

1)帶花樹(shù)一表.......................................................................90

2)帶花樹(shù)一陣.......................................................................93

10.各種回路...........................................................................96

1)CPP_無(wú)向圖.....................................................................96

2)TSP_雙調(diào)歐幾里得................................................................97

3)哈密頓回路_dirac............................................................................................................................98

4)哈密頓回路一競(jìng)賽圖..............................................................100

5)哈密頓路徑一競(jìng)賽圖..............................................................102

6)哈密頓路徑一最優(yōu)&狀壓..........................................................102

11.分治樹(shù)............................................................................104

1)分治樹(shù)—路徑不經(jīng)過(guò)超過(guò)K個(gè)標(biāo)記節(jié)點(diǎn)的最長(zhǎng)路徑..................................104

2)分治樹(shù)_路徑和不超過(guò)K的點(diǎn)對(duì)數(shù).................................................107

3)分治樹(shù)—樹(shù)鏈剖分_Count_hnoi壹036.........................................................................................109

4)分治樹(shù)_QTree壹一樹(shù)鏈剖分.......................................................113

5)分治樹(shù)_P0J3237(QTree壹升級(jí))_樹(shù)鏈剖分.........................................117

6)分治樹(shù)_QTree2一樹(shù)鏈剖分.........................................................122

7)Qtree3..............................................................................................................................................125

8)分治樹(shù)_QTree3(2)一樹(shù)鏈剖分.....................................................128

9)分治樹(shù)_QTree4_他人的..........................................................130

10)分治樹(shù)_QTree5_無(wú)代碼..........................................................135

12.經(jīng)典問(wèn)題..........................................................................135

1)歐拉回路一遞歸.................................................................135

3)同構(gòu)一樹(shù).........................................................................137

4)同構(gòu)一無(wú)向圖....................................................................140

5)同構(gòu)一有向圖....................................................................141

6)弦圖一表.........................................................................143

7)弦圖一陣........................................................................147

8)最大面一樸素....................................................................149

9)最大團(tuán)_快速....................................................................149

10)極大團(tuán).........................................................................150

11)havel定理.....................................................................151

12)Topological...................................................................................................................................151

13)LCA...................................................................................................................................................152

14)LCA2RMQ...........................................................................................................................................154

15)樹(shù)中兩點(diǎn)路徑上最大-最小邊Jarjan擴(kuò)展........................................157

16)樹(shù)上的最長(zhǎng)路徑.................................................................160

17)floyd最小環(huán)...................................................................161

18)支配集—樹(shù)......................................................................162

19)prufer編碼—樹(shù)的計(jì)數(shù)..........................................................164

20)獨(dú)立集_支配集_匹配............................................................165

21)最小截?cái)?......................................................................168

3

最短路徑

Dijkstra之優(yōu)雅stl

#include<queue>

usingnamespacestd;

#definemaxn壹000

structDijkstra{

typedefpair<int,int>T;//first:權(quán)值，second:索弓I

vector<T>E[maxn];//邊

intd[maxn];//最短的路徑

intp[maxn];//父節(jié)點(diǎn)

priority_queue<T,vector<T>,greater<T>>q;

voidclearEdge(){

for(inti=0;i<maxn;i++)

E[i].clear();

}

voidaddEdge(inti,intj,intval){

E[i].push_back(T(val,j));

)

voiddijkstra(ints){

memset(d,壹27,sizeof(d));

memset(p,255,sizeof(p));

while(!q.empty())q.pop();

intu,du,v,dv;

d[s]=0;

P[s]=s;

q.push(T(0,s));

while(!q.empty()){

u=q.top().second;

du=q.top().first;

q-pop0；

if(d[u]!=du)continue;

for(vector<T>::iteratorit=E[u].begin();it!=E[u].end();it++){

v=it->second;

dv=du+it->first;

if(d[v]>dv){

d[v]=dv;

p[v]=u;

q.push(T(dv,v));

}

)

)

}

}；

Dijkstra—模擬數(shù)組

typedefpair<int,int>T;

structNod{

intb,val,next;

voidinit(intb,intval,intnext){

th(b);th(val);th(next);

}

)；

structDijkstra{

Nodbuf[maxm];intlen;//資源

intE[maxn],n;//圖

intd[maxn];//最短距離

voidinit(intn){

th(n);

memset(Er255,sizeof(E));

len=0;

}

voidaddEdge(inta,intb,intval){

buf[len].init(b,val,E[a]);

4

E[a]=len++;

)

voidsolve(ints){

staticpriority_queue<Tzvector<T>,greater<T>>q;

while(!q.empty())q.pop();

memset(d,63,sizeof(d));

d[s]=0;

q.push(T(0,s));

intu,du,v,dv;

while(!q.empty()){

u=q.top().second;

du=q.top().first;

q.pop();

if(du!=d[u])continue;

for(inti=E[u];i!=-壹；i=buf[i].next){

v=buf[i].b;

dv=du+buffi].val;

if(dv<d[v]){

d[v]=dv;

q.push(T(dv,v));

}

)

)

}

}；

Dijkstra陣

〃Dijkstra鄰接矩陣,不用heap!

#definemaxn壹壹0

constintinf=0x3f3f3f3f;

structDijkstra{

intE[maxn][maxn],n;//圖，須手動(dòng)傳入！

intd[maxn],p[maxn];//最短路徑，父親

voidinit(intn){

this->n=n;

memset(Ez63,sizeof(E));

)

voidsolve(ints){

staticboolvis[maxn];

memset(vis,0,sizeof(vis));

memset(d,63,sizeof(d));

memset(pz255,sizeof(p));

d[s]=0;

while(壹){

intu=一壹；

for(inti=0;i<n;i++){

if(!vis[i]&&(u==-S||d[i]<d[u])){

u=i;

)

)

if(u==-壹IId[u]==inf)break;

vis[u]=true;

for(intv=0;v<n;v++){

if(d[u]+E[u][v]<d[v]){

d[v]=d[u]+E[u][v];

p[v]=u;

)

)

)

}

}dij；

5

SPFA優(yōu)化

'**

*以F程序加上了vis優(yōu)化，但沒(méi)有加slf和111優(yōu)化（似乎效果不是很明顯）

*下面是這兩個(gè)優(yōu)化的教程，不難實(shí)現(xiàn)

SPFA的兩個(gè)優(yōu)化

該日志由zkw發(fā)表于2009-02-壹309:03:06

SPFA與堆優(yōu)化的Dijkstra的速度之爭(zhēng)不是一天兩天了，不過(guò)從這次USAC0月賽題來(lái)看，SPFA用在

分層圖上會(huì)比較慢。標(biāo)程是堆優(yōu)化的Dijkstra,我寫(xiě)了一個(gè)非常樸素的SPFA,只能過(guò)6/壹壹個(gè)點(diǎn)。SPFA

是按照FIFO的原則更新距離的，沒(méi)有考慮到距離標(biāo)號(hào)的作用。實(shí)現(xiàn)中SPFA有兩個(gè)非常著名的優(yōu)化：SLF

和LLLo

SLF：SmallLabelFirst策略。

實(shí)現(xiàn)方法是，設(shè)隊(duì)首元素為i,隊(duì)列中要加入節(jié)點(diǎn)J,在dj<=di時(shí)加到隊(duì)首而不是隊(duì)尾，否則和普

通的SPFA一樣加到隊(duì)尾。

LLL：LargeLabelLast策略。

實(shí)現(xiàn)方法是，設(shè)隊(duì)列Q中的隊(duì)首元素為i,距離標(biāo)號(hào)的平均值為avg(d),每次出隊(duì)時(shí)，若di>avg(d),

把i移到隊(duì)列末尾，如此反復(fù)，直到找到一個(gè)i使，di*avg(d)將其出隊(duì)。

加上SLF優(yōu)化后程序多了一行，過(guò)了9/壹壹個(gè)點(diǎn)。你問(wèn)我怎么用SPFAAC這個(gè)題？利用分層圖性

質(zhì)，算完一層再算一層，對(duì)每一層計(jì)算用SPFA,加上上面的優(yōu)化，程序飛快：最強(qiáng)的優(yōu)化要利用題目的特

殊性質(zhì)。

*/

#definemaxn壹0壹。

#definemaxm2壹00壹。

#defineth(x)this->x=x

structNod{

intb,val,next;

voidinit(intb,intval,intnext){

th(b);th(val);th(next);

}

)；

structSPFA{

Nodbuf[maxm];intlen;

intE[maxn],n;

intd[maxn];

voidinit(intn){

th(n);

memset(E,255,sizeof(E));

len=0;

)

voidaddEdge(inta,intb,intval){

buf[len].init(bzval,E[a]);

E[a]=len++;

)

boolsolve(ints){

staticqueue<int>q;

staticintent[maxn];

staticboolvis[maxn];

while(!q.empty())q.pop();

memset(cntz0,sizeof(ent));

memset(dz63,sizeof(d));

memset(vis,0,sizeof(vis));

d[s]=0;

q.push(s);vis[s]=true;

intu,v;

while(!q.empty()){

u=q.front();q.pop();vis[u]=false;

for(inti=E[u];i!=-壹；i=buf[i].next){

v=buf[i].b;

if(d[u]+buf[i].val<d[v]){

6

d[v]=d[u]+buf[i].val;

if(!vis[v]){

q.push(v);vis[v]=true;

)

if(++ent[v]>n)returnfalse;

}

)

)

returntrue;

}

}spfa;

//poj-2983IstheInformationReliable?

//差分約束系統(tǒng)

intmain(){

intnzm;

charc;

inta,b,d;

while(scanf("%d%d"/&n,&m)!=EOF){

spfa.init(n+壹);

for(inti=壹;i<=n;i++){

spfa.addEdge(0,i,0);

)

for(inti=0;i<m;i++){

scanf(*'%c%d%d"z&c,&a,&b);

1

if(c=='V)spfa.addEdge(azb,一壹)；

else{

scanf(n%d",&d);

spfa.addEdge(a,b,-d);

spfa.addEdge(b,a,d);

)

)

if(spfa.solve(0))printf(HReliable\nn);

elseprintf(,,Unreliable\n");

)

return0;

1差分約束系統(tǒng)

1.Xi-Xj<=C[i,j],則j向i連一條邊，權(quán)值為c。

2.加入附加源S,S向每個(gè)點(diǎn)連一條邊，權(quán)值為0。(只是為了保證圖連通)。如果不加附加源也可以，在

SPFA的時(shí)候把所有的d初始化為0,并且所有的點(diǎn)都放入隊(duì)列中。.

然而有的時(shí)候不能所有的d都初始化為0,也不能把所有的點(diǎn)都放入隊(duì)列；這樣的題往往是初始

化一部分d,并且放一部分d到隊(duì)列中，一般用于求極值問(wèn)題；如果是鏈?zhǔn)浇Y(jié)構(gòu)，從一頭不行，就試

試另外一頭。還是憑借感覺(jué)去做。具體的證明【【【待補(bǔ)完】】L

3.從S求解單源最短路徑，到每個(gè)點(diǎn)的d值為它的一個(gè)x可行解。

4.如果{x0,x壹,x2…}是一組可行解，則{xO+d,x壹+d,x2+d…}也是。

5.注意序列益處的問(wèn)題，可以適當(dāng)?shù)恼{(diào)整大小，對(duì)序列加減1操作。

6.如果是很多的離散的變量，可以用￡xi來(lái)讓他們加起來(lái)，并且2xi-￡xi-壹進(jìn)行差分約束

K短路

Readme

K短路小節(jié)：

壹.Yen適合做無(wú)環(huán)的，AStar適合做有環(huán)的

2.Yen不能有重點(diǎn)?。?！!

3.有的圖可能Astar會(huì)死循環(huán)，這時(shí)用Yen最好

K短路—無(wú)環(huán)_Astar

#definemaxn壹0壹0

#definemaxm壹000壹0

7

constintinf=0x3f3f3f3f;

typedefpair<intzint>T;

structTT{

intfirst,second,mask;//保證點(diǎn)的個(gè)數(shù)小于mask的范圍(即30)

TT(intfirst,intsecond,intmask):first(first)rsecond(second),

mask(mask){}

)；

structNod{

intb,val,next;

voidinit(intb,intval,intnext){

this->b=b;

this->val=val;

this->next=next;

}

)；

structDijkstra{

intE[maxn],n;//圖

Nodbuf[maxm];intlen;//資源

intd[maxn];//最短距離

voidinit(intn){

this->n=n;

memset(E,255,sizeof(E));

len=0;

}

voidaddEdge(inta,intb,intval){

buf[len].init(b,val,E[a]);E[a]=len++;

}

voidsolve(ints){

staticpriority_queue<Tzvector<T>zgreater<T>>q;

while(!q.empty())q.pop();

memset(d,63,sizeof(d));

d[s]=0;

q.push(T(0,s));

intu,du,v,dv;

while(!q.empty()){

u=q.top().second;

du=q.top().first;

q-pop();

if(du!=d[u])continue;

for(inti=E[u];i!=-壹；i=buf[i].next){

v=buf[i].b;

dv=du+buf[i].val;

if(dv<d[v]){

d[v]=dv;

q.push(T(dvzv));

)

)

)

}

}；

Dijkstradij;

structcmp{

booloperator()(constTT&a,constTT&b)const{

if(a.first+dij.d[a.second]==b.first+dij.d[b.second])

returna.first>b.first;

returna.first+dij.d[a.second]>b.first+dij.d[b.second];

}

)；

structAStar{//Astar求解k短路

intE[maxn]rn;//圖

Nodbuf[maxm];intlen;//資源

intent[maxn];//記錄次數(shù)

8

voidinit(intn){

this->n=n;

memset(E,255,sizeof(E));

len=0;

dij.init(n);

}

voidaddEdge(inta,intb,intval){

buf[len].init(b,val,E[a]);E[a]=len++;

dij.addEdge(b,a,val);

)

/**

*注釋：

*壹.k=壹是最短路，以此類(lèi)推

*2.k短路和k-壹短路可能相同！

*3.沒(méi)有k短路返回-壹

*/

intsolve(ints,intt,intk){

if(s==t)k++;//假設(shè)兩個(gè)點(diǎn)合并在一起不算路??！

staticpriority_queue<TT,vector<TT>zcmp>q;

while(!q.empty())q.pop();

dij.solve(t);

if(dij.d[s]==inf)return-壹；//根本就沒(méi)有路！

intu,du,v,dv,mask;

memset(ent,0,sizeof(ent));

q.push(TT(0,s,4?s))；//T.first是f(n),T.second是n

while(!q.empty()){

u=q.top().second;

du=q.top().first;

mask=q.top().mask;

q-pop()；

ent[u]++;

//即當(dāng)前是到u點(diǎn)的ent[u]短路

if(t==u){//松弛最后一個(gè)點(diǎn)

printf("%d"，du);〃打印答案

if(ent[t]==k)returndu;

continue;//最后一個(gè)點(diǎn)不許松弛其他點(diǎn)！

}

//if(ent[u]>k)continue;//大于k,我不在需要你了！【不要這句話?。?！】

for(inti=E[u];i!=-壹；i=buf[i].next){

v=buf[i].b;

dv=du+buf[i].val;

if(mask&(壹<<v))continue;

q.push(TT(dv,v,mask|(壹<<v)));//松弛伙伴！

)

)

return-壹；

)

}as;

//SOJ-327壹打印前k短路徑長(zhǎng)度

intmain(){

intn,s,t,tmp,MAX;

while(cin?n>>s?t>>MAX){

if(n>30)while(8);

as.init(n);

for(inti=0;i<n;i++){

9

for(intj=0;j<n;j++){

cin?tmp;

if(i!=j&&tmp!=MAX){

as.addEdge(i,j,tmp);

}

)

}

as?solve(s-壹，t-壹，n);

cout?endl;

)

return0;

}

K短路—無(wú)環(huán)_Yen

/**

*注意：

*壹.求【無(wú)環(huán)】【k短路徑】

*2.不能有【重邊】

★/

constintmaxn=30;

constintinf=0x3f3f3f3f;

typedefpair<intzint>T;

structNod{

intb,nxt,val;

voidinit(intb,intnxt,intval){

this->b=b;

this->nxt=nxt;

this->val=val;

)

)；

structPath{

vector<int>node,block;

intlen;

//Theindexofthedeviationnode.Nodesbeforethisnodeareonthe

//kshortestpaths*tree.

intdev;

booloperator<(constPathsp)const{

returnlen>p.len;

)

)；

structGraph{

intE[maxn],n;//圖

Nodbuf[maxn*maxn];intlen;//資源

voidinit(intn){

this->n=n;

memset(Ez255,sizeof(E));

len=0;

memset(edge,255,sizeof(edge));

)

voidaddEdge(inta,intb,intv){

edge[a][b]=len;

buf[len].init(b,E[a],v);E[a]=len++;

}

//GettheklooplessshortestpathswithYEN*salgorithm.

//Iftwopathshavethesamelength,theonewhosereversedpath

vector<Path>yenLoopless(intsource,intsink,intk){

vector<Path>res;

priority_queue<Path>q;//candidate

memset(block,0,sizeof(block));

initSingleSrc(source);

10

dijkstra();

if(d[sink]<inf){

Pathsh=shortestPath(sink);

sh.dev=壹；

sh.block.push_back(sh.node[sh.dev]);

q.push(sh);

)

while(res.size()<k&&!q.empty()){

Pathpath=q.top();q.pop();

for(intdev=path.dev;dev<path.node.size();dev++){

intpre=path.node[dev-壹];

if(dev==path.dev){

for(inti=0;i<path.block.size();i++){

block[pre][path.block[i]]=true;

)

}else{

block[pre][path.node[dev]]=true;

)

initSingleSrc(source);

delSubpath(path,dev);

dijkstra();

if(d[sink]<inf){

PathnewP=shortestPath(sink);

newP.dev=dev;

if(dev==path.dev){

newP.block=path.block;

}else{

newP.block.push_back(path.node[dev]);

)

newP.block.push_back(newP.node[dev]);

q.push(newP);

}

)