最小生成树，就是从一个有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.转载于:https://www.cnblogs.com/JRX2015U43/p/6533522.html
相关资源：图的最小生成树