csp 201812-4 数据中心

数据中心"/>

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*10⁵,m<=10⁵，所以选用迪杰斯特拉算法。
再有题目所说“但是不能将数据传输给多个节点”，也就是说图中不可能出现环。

代码:

#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数组存储的不是顶点（下标）的最终父亲（比如说它爷爷），而是它是就近父亲（它爹），这样会导致每次查询的时候，都要查一遍它的就近父亲。而上面代码解答中给出的方法就会更新它的内容，让它始终存储它的最终父亲，省下查就近父亲的过程。