ACM 最小生成树 Constructing Roads

╰+攻爆jí腚メ 2022-07-12 01:16 130阅读 0赞

最小生成树：一个有 n 个结点的[连通图][Link 1]的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

最小生成树可以用[kruskal][]（克鲁斯卡尔）算法或[prim][]（普里姆）算法求出。

在一给定的[无向图][Link 2]G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边，而 w(u, v) 代表此[边][Link 3]的权重，若存在 T 为 E 的[子集][Link 4]且为无循环图，使得的 w(T) 最小，则此 T 为 G 的**最小生成树**。最小生成树其实是**最小权重生成树**的简称。

例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

**Prim算法简述**

1).输入：一个加权连通图，其中顶点集合为V，边集合为E；

2).初始化：Vnew= \{x\}，其中x为集合V中的任一节点（起始点），Enew= \{\},为空；

3).重复下列操作，直到Vnew= V：

a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；

b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；

4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。

图例描述:

<table> 
 <tbody> 
 <tr> 
 <th>图例</th> 
 <th>说明</th> 
 <th>不可选</th> 
 <th>可选</th> 
 <th>已选（Vnew）</th> 
 </tr> 
 <tr> 
 <td>&nbsp; <img alt="" height="168" src="http://pic002.cnblogs.com/images/2012/426620/2012073015154494.png" width="200"> </td> 
 <td>此为原始的加权连通图。每条边一侧的数字代表其权值。</td> 
 <td>-</td> 
 <td>-</td> 
 <td>-</td> 
 </tr> 
 <tr> 
 <td> <img alt="" height="168" src="http://pic002.cnblogs.com/images/2012/426620/2012073015175038.png" width="200"> </td> 
 <td>顶点D被任意选为起始点。顶点A、B、E和F通过单条边与D相连。A是距离D最近的顶点，因此将A及对应边AD以高亮表示。</td> 
 <td>C, G</td> 
 <td>A, B, E, F</td> 
 <td>D</td> 
 </tr> 
 <tr> 
 <td>&nbsp; <img alt="" height="168" src="http://pic002.cnblogs.com/images/2012/426620/2012073016090032.png" width="200"> </td> 
 <td>下一个顶点为距离D或A最近的顶点。B距D为9，距A为7，E为15，F为6。因此，F距D或A最近，因此将顶点F与相应边DF以高亮表示。</td> 
 <td>C, G</td> 
 <td>B, E, F</td> 
 <td>A, D</td> 
 </tr> 
 <tr> 
 <td><img alt="" height="168" src="http://pic002.cnblogs.com/images/2012/426620/2012073016130394.png" width="200"></td> 
 <td>算法继续重复上面的步骤。距离A为7的顶点B被高亮表示。</td> 
 <td>C</td> 
 <td>B, E, G</td> 
 <td>A, D, F</td> 
 </tr> 
 <tr> 
 <td>&nbsp; <img alt="" height="168" src="http://pic002.cnblogs.com/images/2012/426620/2012073016143177.png" width="200"> </td> 
 <td>在当前情况下，可以在C、E与G间进行选择。C距B为8，E距B为7，G距F为11。E最近，因此将顶点E与相应边BE高亮表示。</td> 
 <td>无</td> 
 <td>C, E, G</td> 
 <td>A, D, F, B</td> 
 </tr> 
 <tr> 
 <td>&nbsp; <img alt="" height="168" src="http://pic002.cnblogs.com/images/2012/426620/2012073016154616.png" width="200"> </td> 
 <td>这里，可供选择的顶点只有C和G。C距E为5，G距E为9，故选取C，并与边EC一同高亮表示。</td> 
 <td>无</td> 
 <td>C, G</td> 
 <td>A, D, F, B, E</td> 
 </tr> 
 <tr> 
 <td> <img alt="" height="168" src="http://pic002.cnblogs.com/images/2012/426620/2012073016114494.png" width="200"> </td> 
 <td>顶点G是唯一剩下的顶点，它距F为11，距E为9，E最近，故高亮表示G及相应边EG。</td> 
 <td>无</td> 
 <td>G</td> 
 <td>A, D, F, B, E, C</td> 
 </tr> 
 <tr> 
 <td> <img alt="" height="168" src="http://pic002.cnblogs.com/images/2012/426620/2012073016100874.png" width="200"> </td> 
 <td>现在，所有顶点均已被选取，图中绿色部分即为连通图的最小生成树。在此例中，最小生成树的权值之和为39。</td> 
 <td>无</td> 
 <td>无</td> 
 <td>A, D, F, B, E, C, G</td> 
 </tr> 
 </tbody> 
</table>

**Kruskal算法简述**

假设 WN=(V,\{E\}) 是一个含有 n 个顶点的连通网，则按照克鲁斯卡尔算法构造[最小生成树][Link 5]的过程为：先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

**算法简单描述**

1).记Graph中有v个顶点，e个边

2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边

3).将原图Graph中所有e个边按权值从小到大排序

4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中

if （这条边连接的两个节点于图Graphnew中不在同一个连通分量中）

添加这条边到图Graphnew中

图例描述：

![2012073015215729.jpg][]首先第一步，我们有一张图Graph，有若干点和边

![2012073015234045.jpg][]

将所有的边的长度排序，用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序，对局部最优的资源进行选择，排序完成后，我们率先选择了边AD。这样我们的图就变成了右图

![2012073015313195.jpg][]在剩下的变中寻找。我们找到了CE。这里边的权重也是5

![2012073015332154.jpg][]依次类推我们找到了6,7,7，即DF，AB，BE。

![2012073015361536.jpg][]

下面继续选择， BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了（对于BC可以通过CE,EB来连接，类似的EF可以通过EB,BA,AD,DF来接连）。所以不需要选择他们。类似的BD也已经连通了（这里上图的连通线用红色表示了）。

最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是右：

###  ###

### 伪代码 ###

GenerieMST(G)

\{ //求G的某棵MST

T〈-￠； //T初始为空，是指顶点集和边集均空

while T未形成G的生成树

do\{

找出T的一条安全边（u，v）； //即T∪\{(u，v)\}仍为MST的子集

T=T∪\{(u，v)\}； //加入安全边，扩充T

return T； //T为生成树且是G的一棵MST

TOJ 3451: Constructing Roads

There are N villages, which are numbered from 1 to N, and you should build some roads such that every two villages can connect to each other. We say two village A and B are connected, if and only if there is a road between A and B, or there exists a village C such that there is a road between A and C, and C and B are connected.  
  
We know that there are already some roads between some villages and your job is the build some roads such that all the villages are connect and the length of all the roads built is minimum.

输入

The first line is an integer N (3 <= N <= 100), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within \[1, 1000\]) between village i and village j. 
 
Then there is an integer Q (0 <= Q <= N \* (N + 1) / 2). Then come Q lines, each line contains two integers a and b (1 <= a < b <= N), which means the road between village a and village b has been built.

输出

You should output a line contains an integer, which is the length of all the roads to be built such that all the villages are connected, and this value is minimum.

![20170717101427252][]

#include<iostream>
 #include<algorithm>
 #define N 110
 using namespace std;
 
 struct node
 {
 	int u,v,w;
 }edge[N*N];
 int parent[N];
 bool cmp(node a,node b)
 {
 if(a.w<=b.w) return true;
 return false;
 }
 int find(int a)
 {
 if(a!=parent[a])
 return find(parent[a]);
 else return a;
 }
 int kruskal(int n,int m)
 {
 sort(edge,edge+m,cmp);
 int i,x,y,ans=0;
 for(i=0;i<m;i++)
 {
 x=edge[i].u;
 y=edge[i].v;
 x=find(x);
 y=find(y);
 if(x!=y)
 {
 ans+=edge[i].w;
 parent[y]=x;
 }
 }
 return ans;
 }
 int main()
 {
 int n,q,k,i,j,m;
 while(cin>>n)
 {
 m=0;
 for(i=1;i<=n;i++)
 {
 for(j=1;j<=n;j++)
 { 
 cin>>k;
 if(i>=j) continue;
 edge[m].u=i;
 edge[m].v=j;
 edge[m].w=k;
 m++;
 }
 }
 for(k=1;k<=n;k++) parent[k]=k;
 cin>>q;
 for(k=1;k<=q;k++)
 {
 cin>>i>>j;
 i=find(i);
 j=find(j);
 parent[j]=i;
 }
 cout<<kruskal(n,m)<<endl;
 }
 return 0;
 }

[Link 1]: http://baike.baidu.com/view/3148644.htm
[kruskal]: http://baike.baidu.com/view/580403.htm
[prim]: http://baike.baidu.com/view/580409.htm
[Link 2]: http://baike.baidu.com/view/93110.htm
[Link 3]: http://baike.baidu.com/view/132226.htm
[Link 4]: http://baike.baidu.com/view/276935.htm
[Link 5]: http://baike.baidu.com/view/288214.htm
[2012073015215729.jpg]: /images/20220711/45b26b9dbf064159b59acb9f3daedfa4.png
[2012073015234045.jpg]: /images/20220711/1c3609093a874884814b9da107b1723e.png
[2012073015313195.jpg]: /images/20220711/00b011d8012641adb2a2d65ef94be419.png
[2012073015332154.jpg]: /images/20220711/a3846fa96f3049cab456592550835b08.png
[2012073015361536.jpg]: /images/20220711/9353d1051b3e4b52856304ad40cbea6a.png
[20170717101427252]: /images/20220711/d168f5f69ce04f3db4451ab88f35a529.png