1、圖論是ACM競(jìng)賽中比較重要的組成部分，其模型廣泛存在于現(xiàn)實(shí)生活之中。因其表述 形象生動(dòng)，思維方式抽象而不離具體，因此深受各類喜歡使勁 YY的Acmer的喜愛。這篇文章引述圖論中有關(guān)有向圖最小生成樹的部分，具體介紹朱劉算法的求解思路，并結(jié)合一系列coding技巧，實(shí)現(xiàn)最小樹型圖0 (VE)的算法，并在最后提供了該算法的模版，以供參考。關(guān)于最小生成樹的概念，想必已然家喻戶曉。 給定一個(gè)連通圖，要求得到一個(gè)包含所有頂點(diǎn)的樹(原圖的子圖)，使之所構(gòu)成的邊權(quán)值之和最小。在無(wú)向圖中，由于邊的無(wú)向性質(zhì)，所以求解變得十分容易，使用經(jīng)典的kruskal與prim算法已經(jīng)足夠解決這類問(wèn)題。而在有向圖中，則定義要稍

2、微加上一點(diǎn)約束，即以根為起點(diǎn)，沿給定有向邊，可以訪問(wèn)到所有的點(diǎn)，并使所構(gòu)成的邊權(quán)值之和最小，于是問(wèn)題開始變得不一樣了，我們稱之為最小樹型圖問(wèn)題。該問(wèn)題是由朱永津與劉振宏在上個(gè)世紀(jì)60年代解決的，值得一提的是，這 2個(gè)人現(xiàn)在仍然健在，更另人敬佩的是，朱永津幾乎可以說(shuō)是一位盲人。解決最小樹型圖的算法后來(lái)被稱作朱劉算法，也是當(dāng)之無(wú)愧的。首先我們來(lái)闡述下算法的流程：算法一開始先判斷從固定根開始是否可達(dá)所有原圖中的點(diǎn)，若不可，則一定不存在最小樹形圖。這一步是一個(gè)很隨便的搜索，寫多搓都行，不加廢 話。第二步，遍歷所有的邊，從中找出除根結(jié)點(diǎn)外各點(diǎn)的最小入邊，累加權(quán)值，構(gòu)成新圖。 接著判斷該圖是否存在環(huán)。若不

3、存在，則該圖便是所求最小樹型圖，當(dāng)前權(quán)為最小權(quán)。否則對(duì)環(huán)縮點(diǎn)，然后回到第二步繼續(xù)判斷。這里存在一系列細(xì)節(jié)上的實(shí)現(xiàn)問(wèn)題，以確保能夠達(dá)到VE的復(fù)雜度。首先是查環(huán)，對(duì)于新圖來(lái)說(shuō)只有n-1條入邊，對(duì)于各條入邊，其指向的頂點(diǎn)是唯一的，于是我們可以在邊表中 添加from，表示該邊的出發(fā)點(diǎn)，并考慮到如果存在環(huán)，則對(duì)環(huán)上所有邊反向，環(huán)是顯然同 構(gòu)的，于是最多作V次dfs就能在新圖中找到所有的環(huán)，并能在遞歸返回時(shí)對(duì)頂點(diǎn)重標(biāo)號(hào)進(jìn)行縮點(diǎn)，此步的重標(biāo)號(hào)可以用hash數(shù)組映射。然后就是重要的改邊法，對(duì)于所有不在環(huán)上的邊，修改其權(quán)為 w-min(v) ，w為當(dāng)前邊權(quán)，min(v)為當(dāng)前連接v點(diǎn)的最小邊權(quán)。其數(shù)學(xué) 意義在于

4、選擇當(dāng)前邊的同時(shí)便放棄了原來(lái)的最小入邊。我們可以知道，每次迭代選邊操作 O(E)，縮點(diǎn)操作 O(V)，更新權(quán)操作 O(E)，至少使一個(gè)頂點(diǎn)歸入生成樹，于是能在V-1步內(nèi)完成計(jì)算，其復(fù)雜度為 O(VE)。以上為定根最小樹型圖， 對(duì)于無(wú)固定根最小樹型圖，只要虛擬一個(gè)根連所有的點(diǎn)的權(quán)為邊權(quán)總和+1，最后的結(jié)果減去(邊權(quán)+1)即可。另外對(duì)于求所定的根標(biāo)號(hào)，只要搜索被選中 的虛邊就可以判斷了。#in elude <cstdio>#in elude <iostream>#in elude <cmath>#in elude <estri ng>using n

5、amespaee std;con st int N=101,M=10001,i nf=2147483647;struet edge int u,v,w; eM;int n,m,a ns,idN,preN,vN,i nwN;void zhu_liu(i nt root)int s,t,idx =n;while (idx)for (int i=1;i<=n;+i) in wi=i nf,idi=-1,vi=-1; for (int i=1;i<=m;+i)s=ei.u;t=ei.v;if (ei.w> in wt | s=t) continue; pret=s;in wt=ei.

6、w;in wroot=0;preroot=root;for (int i=1;i<=n;+i)if (in wi=i nf)prin tf("impossiblen");return;an s+=in wi;idx=0;for (int i=1;i<=n;+i)if (vi=-1)t=i;while (vt=-1) vt=i,t=pret; if (vt!=i | t=root) continue; idt=+idx;for (s=pret;s!=t;s=pres) ids=idx;if (idx=O) con ti nue;for (int i=1;i<=n;+i)if (idi=-1) idi=+idx;for (int i=1;i<=m;+i)ei.w-=i nwei.v;ei.u=idei.u;ei.v=idei.v;n=idx;root=idroot;prin tf("%dn",a ns);int mai n()scan f("%d%d",&n,&m);for (in t i=1;i<=m;+i)scan f("%d%d%d", &ei.u, &ei.v, &ei.w); zhuiu(1);return