更多的可以參考我的博客锯茄，也在陸續(xù)更新ing
http://www.hspweb.cn/
例子是最小差值生成樹:
給定一個無向圖缺脉，求它的一棵最小生成樹溃斋，使得生成樹中的最大邊權(quán)與最小邊權(quán)的差最小化庸疾。
4 6（定點數(shù)，邊數(shù)两嘴。下面是帶權(quán)值的鄰接矩陣）
2 1 22409496
3 1 601062
3 2 1474032
4 1 64697574
4 2 53913408
4 3 26249836
思路：
枚舉每一條邊丛楚，作為生成樹中最小邊權(quán)的的邊，在此基礎求得多棵生成樹憔辫，每次用Kruskal算法構(gòu)造最小生成樹趣些，用最大權(quán)值減去最小權(quán)值作為答案輸出。而在Kruskal算法中用到并查集贰您。
1.先上并查集的基本思想坏平。
并查集由一個整數(shù)型的數(shù)組和兩個函數(shù)構(gòu)成。數(shù)組pre[]記錄了每個點的前導點是什么锦亦，函數(shù)find是查找舶替，join是合并。
int pre[1010]; //存放第i個元素的父節(jié)點
int unionsearch(int root) //查找根結(jié)點
{
int son, tmp;
son = root;
while(root != pre[root]) //尋找根結(jié)點
root = pre[root];
while(son != root) //路徑壓縮
{
tmp = pre[son];
pre[son] = root;
son = tmp;
}
return root;
}
void join(int root1, int root2) //判斷是否連通孽亲，不連通就合并
{
int x, y;
x = unionsearch(root1);
y = unionsearch(root2);
if(x != y) //如果不連通坎穿，就把它們所在的連通分支合并
pre[x] = y;
}
2. 趣解并查集
話說江湖上散落著各式各樣的大俠，有上千個之多返劲。他們沒有什么正當職業(yè)玲昧，整天背著劍在外面走來走去，碰到和自己不是一路人的篮绿，就免不了要打一架孵延。但大俠們有一個優(yōu)點就是講義氣，絕對不打自己的朋友亲配。而且他們信奉“朋友的朋友就是我的朋友”尘应，只要是能通過朋友關(guān)系串聯(lián)起來的，不管拐了多少個彎吼虎，都認為是自己人犬钢。這樣一來，江湖上就形成了一個一個的幫派思灰，通過兩兩之間的朋友關(guān)系串聯(lián)起來玷犹。而不在同一個幫派的人，無論如何都無法通過朋友關(guān)系連起來洒疚，于是就可以放心往死了打歹颓。但是兩個原本互不相識的人坯屿，如何判斷是否屬于一個朋友圈呢？
我們可以在每個朋友圈內(nèi)推舉出一個比較有名望的人巍扛，作為該圈子的代表人物领跛。這樣，每個圈子就可以這樣命名“中國同胞隊”美國同胞隊”……兩人只要互相對一下自己的隊長是不是同一個人撤奸，就可以確定敵友關(guān)系了吠昭。
但是還有問題啊，大俠們只知道自己直接的朋友是誰寂呛，很多人壓根就不認識隊長抓狂要判斷自己的隊長是誰怎诫，只能漫無目的的通過朋友的朋友關(guān)系問下去：“你是不是隊長？你是不是隊長贷痪？”這樣幻妓，想打一架得先問個幾十年，餓都餓死了劫拢，受不了肉津。這樣一來，隊長面子上也掛不住了舱沧，不僅效率太低妹沙，還有可能陷入無限循環(huán)中。于是隊長下令熟吏，重新組隊距糖。隊內(nèi)所有人實行分等級制度，形成樹狀結(jié)構(gòu)牵寺，我隊長就是根節(jié)點悍引，下面分別是二級隊員、三級隊員帽氓。每個人只要記住自己的上級是誰就行了趣斤。遇到判斷敵友的時候，只要一層層向上問黎休，直到最高層浓领，就可以在短時間內(nèi)確定隊長是誰了。由于我們關(guān)心的只是兩個人之間是否是一個幫派的势腮，至于他們是如何通過朋友關(guān)系相關(guān)聯(lián)的联贩，以及每個圈子內(nèi)部的結(jié)構(gòu)是怎樣的，甚至隊長是誰捎拯，都不重要了撑蒜。所以我們可以放任隊長隨意重新組隊，只要不搞錯敵友關(guān)系就好了。于是座菠，門派產(chǎn)生了。
下面我們來看并查集的實現(xiàn)藤树。 int pre[1000]; 這個數(shù)組浴滴，記錄了每個大俠的上級是誰。大俠們從1或者0開始編號（依據(jù)題意而定）岁钓，pre[15]=3就表示15號大俠的上級是3號大俠升略。如果一個人的上級就是他自己，那說明他就是掌門人了屡限，查找到此為止品嚣。也有孤家寡人自成一派的，比如歐陽鋒钧大，那么他的上級就是他自己翰撑。每個人都只認自己的上級。比如胡青牛同學只知道自己的上級是楊左使啊央。張無忌是誰眶诈？不認識！要想知道自己的掌門是誰瓜饥，只能一級級查上去逝撬。
find這個函數(shù)就是找掌門用的，意義再清楚不過了（路徑壓縮算法先不論乓土，后面再說）宪潮。
int unionsearch(int root) //查找根結(jié)點
{
int son, tmp;
son = root;
while(root != pre[root]) //我的上級不是掌門
root = pre[root];
while(son != root) //我就找他的上級，直到掌門出現(xiàn)
{
tmp = pre[son];
pre[son] = root;
son = tmp;
}
return root; //掌門駕到~~
}
再來看看join函數(shù)趣苏，就是在兩個點之間連一條線狡相，這樣一來，原先它們所在的兩個板塊的所有點就都可以互通了拦键。這在圖上很好辦谣光，畫條線就行了。但我們現(xiàn)在是用并查集來描述武林中的狀況的芬为，一共只有一個pre[]數(shù)組萄金，該如何實現(xiàn)呢书在？ 還是舉江湖的例子鞭光，假設現(xiàn)在武林中的形勢如圖所示。虛竹帥鍋與周芷若MM是我非常喜歡的兩個人物另凌，他們的終極boss分別是玄慈方丈和滅絕師太询张，那明顯就是兩個陣營了孙乖。我不希望他們互相打架，就對他倆說：“你們兩位拉拉勾，做好朋友吧唯袄⊥淝”他們看在我的面子上，同意了恋拷。這一同意可非同小可资厉，整個少林和峨眉派的人就不能打架了。這么重大的變化蔬顾，可如何實現(xiàn)呀宴偿，要改動多少地方？其實非常簡單诀豁，我對玄慈方丈說：“大師窄刘，麻煩你把你的上級改為滅絕師太吧。這樣一來舷胜，兩派原先的所有人員的終極boss都是師太娩践，那還打個球啊逞带！大笑反正我們關(guān)心的只是連通性欺矫，門派內(nèi)部的結(jié)構(gòu)不要緊的≌姑ィ”玄慈一聽肯定火大了：“我靠穆趴，憑什么是我變成她手下呀，怎么不反過來遇汞？我抗議未妹！”于是，兩人相約一戰(zhàn)空入，殺的是天昏地暗络它，風云為之變色啊，但是啊歪赢，這場戰(zhàn)爭終究會有勝負化戳，勝者為王。弱者就被吞并了埋凯。反正誰加入誰效果是一樣的点楼，門派就由兩個變成一個了。這段函數(shù)的意思明白了吧白对？
void join(int root1, int root2) //虛竹和周芷若做朋友
{
int x, y;
x = unionsearch(root1);//我老大是玄慈
y = unionsearch(root2);//我老大是滅絕
if(x != y)
pre[x] = y; //打一仗掠廓，誰贏就當對方老大
}
再來看看路徑壓縮算法。建立門派的過程是用join函數(shù)兩個人兩個人地連接起來的甩恼，誰當誰的手下完全隨機蟀瞧。最后的樹狀結(jié)構(gòu)會變成什么樣沉颂，我也無法預知，一字長蛇陣也有可能悦污。這樣查找的效率就會比較低下铸屉。最理想的情況就是所有人的直接上級都是掌門，一共就兩級結(jié)構(gòu)塞关，只要找一次就找到掌門了抬探。哪怕不能完全做到，也最好盡量接近帆赢。這樣就產(chǎn)生了路徑壓縮算法。
設想這樣一個場景：兩個互不相識的大俠碰面了线梗，想知道能不能干一場椰于。 于是趕緊打電話問自己的上級：“你是不是掌門？” 上級說：“我不是呀仪搔，我的上級是誰誰誰瘾婿，你問問他看看】具郑” 一路問下去偏陪，原來兩人的最終boss都是東廠曹公公。 “哎呀呀煮嫌，原來是自己人笛谦，有禮有禮，在下三營六組白面葫蘆娃!” “幸會幸會昌阿，在下九營十八組仙子狗尾巴花饥脑！” 兩人高高興興地手拉手喝酒去了。 “等等等等懦冰，兩位大俠請留步灶轰，還有事情沒完成呢！”我叫住他倆刷钢。 “哦笋颤，對了，還要做路徑壓縮内地“槌危”兩人醒悟。 白面葫蘆娃打電話給他的上級六組長：“組長啊瓤鼻，我查過了秉版，其實偶們的掌門是曹公公。不如偶們一起結(jié)拜在曹公公手下吧茬祷，省得級別太低清焕，以后查找掌門麻煩。” “唔秸妥，有道理滚停。” 白面葫蘆娃接著打電話給剛才拜訪過的三營長……仙子狗尾巴花也做了同樣的事情粥惧。 這樣键畴，查詢中所有涉及到的人物都聚集在曹公公的直接領導下。每次查詢都做了優(yōu)化處理突雪，所以整個門派樹的層數(shù)都會維持在比較低的水平上起惕。路徑壓縮的代碼，看得懂很好咏删，看不懂可以自己模擬一下惹想，很簡單的一個遞歸而已《胶總之它所實現(xiàn)的功能就是這么個意思嘀粱。
于是，問題圓滿解決辰狡。锋叨。。宛篇。娃磺。。些己。豌鸡。。
代碼如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int pre[1010]; //里面全是掌門
int unionsearch(int root)
{
int son, tmp;
son = root;
while(root != pre[root]) //尋找掌門ing……
root = pre[root];
while(son != root) //路徑壓縮
{
tmp = pre[son];
pre[son] = root;
son = tmp;
}
return root; //掌門駕到~
}
int main()
{
int num, road, total, i, start, end, root1, root2;
while(scanf("%d%d", &num, &road) && num)
{
total = num - 1; //共num-1個門派
for(i = 1; i <= num; ++i) //每條路都是掌門
pre[i] = i;
while(road--)
{
scanf("%d%d", &start, &end); //他倆要結(jié)拜
root1 = unionsearch(start);
root2 = unionsearch(end);
if(root1 != root2) //掌門不同段标？踢館涯冠！~
{
pre[root1] = root2;
total--; //門派少一個，敵人（要建的路）就少一個
}
}
printf("%d\n", total);//天下局勢：還剩幾個門派
}
return 0;
}
3.簡單描述一下最小生成樹
在n個頂點的無向圖G<V,E>中逼庞，選擇權(quán)值最小的邊蛇更，一共n-1條，把所有的頂點連接起來赛糟。如圖：
4.簡單描述一下Kruskal算法
Kruskal算法是基于貪心的思想得到的派任。目的就是構(gòu)造最小生成樹。首先我們把所有的邊按照權(quán)值先從小到大排列璧南，接著按照順序選取每條邊掌逛，如果這條邊的兩個端點不屬于同一集合，那么就將它們合并司倚，直到所有的點都屬于同一個集合為止豆混。
5.再回到這個題目
了解了并查集篓像，問題就好辦了。Kruskal算法正是用并查集的find（）查找根節(jié)點皿伺，join（）合并根節(jié)點構(gòu)造最小生成樹员辩。
上面給的4條邊，6個頂點鸵鸥。一共構(gòu)造如下4棵生成樹：
解題代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=200;
const int MAXM=5000;
int pnt[MAXN+1],myrank[MAXN+1];
struct Edge{
int u,v,w;
bool operator<(const Edge &e)const{
return w<e.w;
}
};
Edge edge[MAXM];
int find(int x){
int px=pnt[x];
while(px!=pnt[px]){
px=pnt[px];
}
while(x!=px){
int tmp=pnt[x];
pnt[x]=px;
x=tmp;
}
return px;
}
void merge(int x,int y){
if(myrank[x]<myrank[y]){
pnt[x]=y;
}
else{
pnt[y]=x;
myrank[x]+=(myrank[x]==myrank[y]);
}
}
int main(){
int casen;
scanf("%d",&casen);
while(casen--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
}
sort(edge,edge+m);
int ans=-1;
for(int k=0;k<m;k++){
if(k>0&&edge[k].w==edge[k-1].w){
continue;
}
for(int i=1;i<=n;i++){
myrank[pnt[i]=i]=0;
}
int cnt=0;
for(int i=k;i<m;i++){
int u=find(edge[i].u);
int v=find(edge[i].v);
if(u!=v){
merge(u,v);
cnt++;
printf("cnt is %d\n",cnt);
if(cnt==n-1){
int t=edge[i].w-edge[k].w;
printf("最大邊%d -最小邊%d= %d\n",edge[i].w,edge[k].w,t);
if(ans==-1||ans>t){
ans=t;
}
break;
}
}
}
if(cnt<n-1){
break;
}
}
printf("answer is %d\n",ans);
}
return 0;
}
運行截圖：
并查集部分解釋來自：http://blog.csdn.net/niushuai666/article/details/6662911
