赞
踩
题目给出一个无向连通图,要求求出其最小生成树的权值。
温馨提示:本题请使用kruskal最小生成树算法。
第一行包含两个整数 N(1<=N<=1x106),M(1<=M<=1x106) 表示该图共有 N 个结点和 M 条无向边。
接下来 M 行每行包含三个整数 Xi,Yi,Zi ,表示有一条长度为 Zi 的无向边连接结点 Xi,Yi 。
输出一个整数表示最小生成树的各边的长度之和。
- 4 5
- 1 2 2
- 1 3 2
- 1 4 3
- 2 3 4
- 3 4 3
7
- #include<bits/stdc++.h>
- using namespace std;
- #define maxx 1000010//这里需要7位数
-
- //定一结构体数组来存每组数据
- struct Node{
- int from;
- int to;
- int val;
-
- }node[maxx];
-
- int father[maxx];
-
- bool sort_val(Node a,Node b){
- return a.val < b.val;
- }
-
- //查询元素的根节点
- int find( int a ){
- int r=a;
- while(father[r]!=r)
- r=father[r]; //找到他的前导结点
- int i=a,j;
- while(i!=r){ //路径压缩算法
- j=father[i]; //记录x的前导结点
- father[i]=r; //将i的前导结点设置为r根节点
- i=j;
- }
- return r;
- }
-
-
- //合并根节点不同的联通分量
- void merg(int a,int b){
-
- // int a = find(x);//查询x的根节点
- // int b = find(y);//查询y的根节点
-
- // if(a != b){
- father[a] = b;
- // }
- }
-
- int main(){
-
- int n,m;
- int sum = 0;
-
- //cin >> n >> m;
- scanf("%d%d",&n,&m);
-
- //初始化father数组 将其每个顶点的根节点设置为自己的节点号
- for(int i = 1; i <= n; i++){
- father[i] = i;
- }
-
- for(int i = 0; i < m; i++){
- //cin >> node[i].from >> node[i].to >> node[i].val;
- scanf("%d%d%d",&node[i].from,&node[i].to,&node[i].val);
- }
-
- sort(node,node+m,sort_val);
-
- // for(int i = 0; i < m; i++){
- // cout << node[i].val << endl;
- // }
-
- int count = 0;
-
- for(int i = 0; i < m; i++){
- if(count == n - 1){//n个顶点需要 n - 1边
- break;
- }
- int a = find(node[i].from);
- int b = find(node[i].to);
- if(a != b){
- father[a] = b;
- sum += node[i].val;
- count++;
- }
-
- }
- printf("%d",sum);
- // cout << sum;
- }
-
-
-
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。