最小生成树，就是从一个有N个结点的连通图中找出N-1条边，使这个图仍然连通且这N-1条边的权值总和最小。
1、Prim算法
每找到一个点，就在这个点连接的边中找一条最小的加入生成树，当生成树中有了N-1条边后结束。算法复杂度O(N^2)
2、Kruskal算法
把所有边排序，每次选择一条权值最小且未加入树的边加入生成树，当生成树中有了N个结点后结束。算法复杂度O(NlogN)
在实际应用中，Kruskal算法更加实用。
局域网
【题目描述】
某个局域网内有n(n<=100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)<=1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。
【输入格式】
第一行两个正整数n，k
接下来的k行每行三个正整数i j m表示i,j两台计算机之间有网线联通，通畅程度为m。
【输出格式】
一个正整数，Σf(i,j)的最大值
【样例输入】
5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2
【样例输出】
8
【分析】
此题可以用Kruskal算法解决。
var
i,n,m,ans,root1,root2:longint;
elen,eu,ev,father:array[0..10001]of longint;
procedure qsort(l,r:longint);//把边排序
var
i,j,temp,mid:longint;
begin
i:=l; j:=r;
mid:=elen[(l+r) div 2];
repeat
while elen[i]<mid do inc(i);
while elen[j]>mid do dec(j);
if i<=j then
begin
temp:=elen[i];elen[i]:=elen[j];elen[j]:=temp;
temp:=eu[i];eu[i]:=eu[j];eu[j]:=temp;
temp:=ev[i];ev[i]:=ev[j];ev[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function getfather(x:longint):longint;//并查集操作，可以快速判断两个结点是否都已加入生成树
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
begin
readln(n,m);
for i:=1 to m do readln(eu[i],ev[i],elen[i]);
qsort(1,m);
ans:=0;
for i:=1 to n do father[i]:=i;
for i:=1 to m do begin
root1:=getfather(eu[i]); root2:=getfather(ev[i]);
if root1=root2 then ans:=ans+elen[i] else father[root1]:=root2;
end;
write(ans);
end.鱼塘放水
【题目描述】
庆庆的伯伯承包一个大鱼塘，为了可以放养不同的鱼，鱼塘被分割成N行M列，共有N*M个独立的小池子。各小池子都有独立的进水管，根据放养的鱼种类的不同，控制各小池子的水位。
相邻的小池子之间都有涵洞想通，涵洞配有水闸，水闸平时都是关闭的。只有到换水的时候，才打开某些水闸（涵洞口还有栅栏，你不用担心鱼儿逃跑啦），然后从其中一个小池子（一般都是旁边的小池子）抽水，就可以将整个鱼塘的水换掉。
打开某一个水闸的代价同这个水闸两侧的水位差相一致。在放水前，可以在电控设备上设置好需要打开哪些闸门，按下启动按钮后，同一时间开启需要打开的水闸。
已知各小池子的水位，庆庆想知道开启水闸，开始换水的最小代价，请你帮助他。
【输入格式】
第1行，两个数，表示N和M。
以下N行，每行M个整数X，表示各小池子的水位。
【输出格式】
一个整数，表示开启水闸换水的最小代价。
【样例输入】
3 4
3 5 2 1
7 3 4 8
1 6 5 7
【样例输出】
22
【数据范围】
1<=N,M <=100
0<=X<=100
【分析】
基本是裸的最小生成树，但是注意如何处理边。
如上图所示，每一个鱼池只可以向右、下方向拓展出一条边（为了保证没有重复的边），于是样例中有17条边。
在第N行和第M列，每个鱼池只能向右（下）拓展一条边，这里要注意下标不能写错。
var
i,j,t,n,m,ans,root1,root2:longint;
father,elen,eu,ev:array[0..100001]of longint;
map:array[0..1001,0..1001]of longint;
procedure qsort(l,r:longint);
var
i,j,temp,mid:longint;
begin
if l>=r then exit;
i:=l; j:=r;
mid:=elen[(l+r) div 2];
repeat
while elen[i]<mid do inc(i);
while elen[j]>mid do dec(j);
if i<=j then//按照边的权值排序的时候注意要整体排序
begin
temp:=elen[i];elen[i]:=elen[j];elen[j]:=temp;
temp:=eu[i];eu[i]:=eu[j];eu[j]:=temp;
temp:=ev[i];ev[i]:=ev[j];ev[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);//并查集的路径压缩
exit(father[x]);
end;
begin
readln(t,m);
for i:=1 to t do
for j:=1 to m do
read(map[i,j]);
n:=0;
for i:=1 to t-1 do
for j:=1 to m-1 do
begin
inc(n);eu[n]:=(i-1)*m+j;ev[n]:=i*m+j;elen[n]:=abs(map[i,j]-map[i+1,j]);
inc(n);eu[n]:=(i-1)*m+j;ev[n]:=(i-1)*m+j+1;elen[n]:=abs(map[i,j]-map[i,j+1]);//算出起点和终点的序号，强烈建议亲自动手计算
end;
for i:=1 to t-1 do begin
inc(n);
eu[n]:=i*m;ev[n]:=(i+1)*m;elen[n]:=abs(map[i,m]-map[i+1,m]);
end;
for i:=1 to m-1 do begin
inc(n);
eu[n]:=(t-1)*m+i;ev[n]:=(t-1)*m+i+1;elen[n]:=abs(map[t,i]-map[t,i+1]);
end;
qsort(1,n);
ans:=0;
for i:=1 to n do ans:=ans+elen[i];
for i:=1 to t*m do father[i]:=i;
for i:=1 to n do begin
root1:=getfather(eu[i]); root2:=getfather(ev[i]);
if root1=root2 then ans:=ans-elen[i] else father[root1]:=root2;
end;//和上一题不同的是这题求的是最小生成树里边的权值，而上一题求得是剔除的边的权值，我就在这里被坑了一下
write(ans);
end.繁忙的都市
【题目描述】
城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有n个交叉路口，有些交叉路口之间有道路相连，两个交叉路口之间最多有一条道路相连接。这些道路是双向的，且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值，分值越小表示这个道路越繁忙，越需要进行改造。但是市政府的资金有限，市长希望进行改造的道路越少越好，于是他提出下面的要求：
1．改造的那些道路能够把所有的交叉路口直接或间接的连通起来。
2．在满足要求1的情况下，改造的道路尽量少。
3．在满足要求1、2的情况下，改造的那些道路中分值最大的道路分值尽量小。
任务：作为市规划局的你，应当作出最佳的决策，选择那些道路应当被修建。
【输入格式】
第一行有两个整数n,m表示城市有n个交叉路口，m条道路。接下来m行是对每条道路的描述，u, v, c表示交叉路口u和v之间有道路相连，分值为c。(1≤n≤300，1≤c≤10000)
【输出格式】
两个整数s, max，表示你选出了几条道路，分值最大的那条道路的分值是多少。
【样例输入】
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
【样例输出】
3 6
【分析】
从小到大排序选取较小的边，判断它是否与已选取的边形成回路，直到找到n-1条边。
var
i,n,m,ans,root1,root2:longint;
elen,eu,ev,father:array[0..10001]of longint;
procedure qsort(l,r:longint);
var
i,j,temp,mid:longint;
begin
i:=l; j:=r;
mid:=elen[(l+r) div 2];
repeat
while elen[i]<mid do inc(i);
while elen[j]>mid do dec(j);
if i<=j then
begin
temp:=elen[i];elen[i]:=elen[j];elen[j]:=temp;
temp:=eu[i];eu[i]:=eu[j];eu[j]:=temp;
temp:=ev[i];ev[i]:=ev[j];ev[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
function getfather(x:longint):longint;
begin
if father[x]=x then exit(x);
father[x]:=getfather(father[x]);
exit(father[x]);
end;
begin
readln(n,m);
for i:=1 to m do readln(eu[i],ev[i],elen[i]);
qsort(1,m);
ans:=0;
for i:=1 to n do father[i]:=i;
for i:=1 to m do begin
root1:=getfather(eu[i]); root2:=getfather(ev[i]);
if root1<>root2 then begin
father[root1]:=root2;
inc(ans);
if ans=n-1 then begin ans:=elen[i];break; end;
end;
end;
write(n-1,' ',ans);
end.