数据中心"/>
csp 201812-4 数据中心
样例输入
4
5
1
1 2 3
1 3 4
1 4 5
2 3 8
3 4 2
样例输出
4
样例说明
下图是样例说明。
思路:
很明显题意是求一个求最小生成树的最大边,求最小生成树有迪杰斯特拉算法和普利姆算法。
1)普利姆算法从顶点出发,最大要循环n次。
2)迪杰斯特拉算法从边出发,最大要循环n-1次。
再结合题目所说n<=5*105,m<=105,所以选用迪杰斯特拉算法。
再有题目所说“但是不能将数据传输给多个节点”,也就是说图中不可能出现环。
代码:
#include <stdio.h>
#include <stdlib.h>typedef struct{int vi;int ui;int ti;
} Edge;Edge edge[100000];
int father[100001];int cmp(const void* a,const void* b);
int kruskal(int n,int m);
int find(int v); int main(){int m,n,i,root;scanf("%d",&n);scanf("%d",&m);scanf("%d",&root);for(i=0; i<m; i++){scanf("%d %d %d",&edge[i].vi,&edge[i].ui,&edge[i].ti);}qsort(edge,m,sizeof(Edge),cmp);for(i=1; i<=n; i++) father[i]=i;printf("%d",kruskal(n,m));return 0;
} int cmp(const void* a,const void* b){return ((Edge*)a)->ti - ((Edge*)b)->ti;
}int kruskal(int n,int m){int i,max=0,vif,uif,times=0;for(i=0; i<m; i++){vif = find(edge[i].vi);uif = find(edge[i].ui);if(vif != uif){father[uif] = vif;times++;max = edge[i].ti;}if(times==n-1) break;}return max;
}int find(int v){return father[v] == v? father[v]:(father[v]=find(father[v]));
}
特别说明:
int find(int v){while(father[v] != v){v = father[v];}return v;
}
这样书写find函数是可以得到结果的,但会超时。原因是这种写法中,father数组存储的不是顶点(下标)的最终父亲(比如说它爷爷),而是它是就近父亲(它爹),这样会导致每次查询的时候,都要查一遍它的就近父亲。而上面代码解答中给出的方法就会更新它的内容,让它始终存储它的最终父亲,省下查就近父亲的过程。
更多推荐
csp 201812-4 数据中心
发布评论