问题描述
试题编号：201812-4试题名称：数据中心时间限制：1.0s内存限制：512.0MB问题描述：样例输入
4 5 1 1 2 3 1 3 4 1 4 5 2 3 8 3 4 2
样例输出
4
样例说明
下图是样例说明。
求最小生成树的最长边（事实证明root什么用都没有）
每个节点都需要选择一条路径将数据发送到root号节点：每个点到root都可达
求最优的树结构，使完成这个任务所需时间最短：所有边的和最短
联系到最小生成树。
最后要求的结果是，先求同样深度的点做接收点时的边的最大值，比如深度为1时，边有1，2，4，最大为4，深度为2是便有1，1，2，最大为3……，最后再求这些最大值中的最大值。简化一下就是求最小生成树的所有边的最大值
注意点的编号是从1开始的不是0.。。。
Kruskal算法：
#include<iostream> #include<algorithm> using namespace std; const int MAXN=500005; const int MAXM=100005; struct Edge{ int from; int to; int length; bool operator <(Edge x) const{ return length<x.length; } }; Edge edge[MAXM]; //边集合 int father[MAXN]; //父亲节点 int height[MAXN]; void Init(int n){ //初始化 for(int i=1;i<=n;i++){ //注意是小于等于，因为编号从1开始的 father[i]=i; height[i]=0; } } int Find(int x){ //查找根节点 if(x!=father[x]){ father[x]=Find(father[x]); } return father[x]; } void Union(int x,int y){ //合并集合 x=Find(x); y=Find(y); if(x!=y){ if(height[x]<height[y]){ father[x]=y; } else if(height[y]<height[x]){ father[y]=x; } else{ father[y]=x; height[x]++; } } return ; } int Kruskal(int n,int edgeNumber){ Init(n); sort(edge,edge+edgeNumber); //按权值排序 int ans=0; for(int i=0;i<edgeNumber;i++){ if(Find(edge[i].from)!=Find(edge[i].to)){ //一条边的两个点分别在两个集合 Union(edge[i].from,edge[i].to); ans=max(ans,edge[i].length); } } return ans; } int main(){ int n,m,root; scanf("%d%d%d",&n,&m,&root); for(int i=0;i<m;i++){ int u,v,t; scanf("%d%d%d",&u,&v,&t); edge[i].from=u; edge[i].to=v; edge[i].length=t; } printf("%d\n",Kruskal(n,m)); return 0; }Prime算法
/* Prime算法的思想是： 首先以一个结点作为最小生成树的初始结点， 然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。 （加入之后如果产生回路了就要跳过这条边，选择下一个结点） 当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树～ */ #include<iostream> #include<queue> using namespace std; const int MAXN=500005; const int MAXM=100005; struct Edge{ int from; int to; int length; bool operator <(Edge x) const{ //优先队列是大顶堆，这里要把大顶堆变成小顶堆 return length>x.length; } }; vector<Edge> adj[MAXN]; //edge[i]表示以i节点为起始点的边 priority_queue<Edge> temp; //按照边的权值大小排序 vector<Edge> tree; //存储最小生成树 int visited[MAXN]; //该点是否被访问过，访问过=1，否则=0 void visit(int x){ //x的visited置一，并将以x为起始点的所有边加入到temp中 visited[x]=1; for(int i=0;i<adj[x].size();i++){ if(visited[adj[x][i].to]==0){ //该边的终点未被访问过 temp.push(adj[x][i]); } } } int Prime(){ visit(1); //以节点1为起始节点 int ans=0; while(!temp.empty()){ Edge e=temp.top(); temp.pop(); if(visited[e.to]==0){ //该点未被访问过，访问该点 visit(e.to); temp.push(e); ans=max(ans,e.length); } } return ans; } int main(){ int n,m,root; scanf("%d%d%d",&n,&m,&root); for(int i=0;i<m;i++){ int u,v,t; scanf("%d%d%d",&u,&v,&t); Edge e; e.from=u,e.to=v,e.length=t; adj[u].push_back(e); e.from=v,e.to=u,e.length=t; adj[v].push_back(e); } printf("%d\n",Prime()); return 0; }
