CCF201812-4 数据中心（最小生成树）

问题描述

问题解析：

        我在考试时在纠结这题是到底是最小生成树还是迪杰斯特拉，因为这题我第一眼看上去像是个单源最短路径问题，但是后来看了题目给的样例说明后才明白，这个树结构构造好之后，是一个最小生成树。所以最后还是用最小生成树做。本题要求的是最大传输时间，即最小生成树中边的最大权重，侧重边，所以用克鲁斯卡尔算法。

解题思路：

        清楚了这道题要用克鲁斯卡尔算法，后面的编码就非常简单了，注意要做路径优化。克鲁斯卡尔算法详解

C++代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{int a,b,v;node(int s,int e,int c){a=s;b=e;v=c;}
};
vector<node> edge;
int pre[50001];
int find(int a)
{int x=a;while(x!=pre[x])x=pre[x];while(pre[a]!=x)	//路径优化，使寻根过程中遇到的每个点的根节点都设成最深处的那个根 {int temp=pre[a];pre[a]=x;a=temp;}return x;
}
bool cmp(node a,node b)
{return a.v<b.v;
}
int main()
{int s,e,c,count=0,res=0;int n,m,root;cin>>n>>m>>root;for(int i=0;i<n;i++)pre[i]=i;for(int i=0;i<m;i++){cin>>s>>e>>c;edge.push_back(node(s,e,c));}sort(edge.begin(),edge.end(),cmp);for(int i=0;i<edge.size();i++){int fa=find(edge[i].a);int fb=find(edge[i].b);if(fa!=fb){res=res>edge[i].v?res:edge[i].v;pre[fa]=fb;count++;if(count==n*(n-1)/2)	//最小生成树的边数是n*(n-1)/2，可以提前跳出循环节省时间。 break;}}cout<<res;return 0;
}