首页 > 代码库 > Sicily 7766:Dark roads(最小生成树)
Sicily 7766:Dark roads(最小生成树)
#include<bits/stdc++.h> using namespace std; struct Vertex{ int start, end; int weight; }; Vertex arr[200010]; int par[200010]; int n, m; long long cost = 0; int find(int n){ while(par[n] != n){ n = par[n]; } return n; } void merge(int n1, int n2){ while(par[n1] != n1){ n1 = par[n1]; par[n1] = n2; } par[n1] = n2; } bool cmp(Vertex v1, Vertex v2){ return v1.weight < v2.weight; } long long func(){ int ans = 0; sort(arr, arr+m, cmp); int i = 0; int k = 0; while(k < m){ Vertex tmp = arr[k++]; int n1 = find(tmp.start); int n2 = find(tmp.end); if(n1 == n2){ continue; } else{ cost += tmp.weight; if(n1 > n2)swap(n1, n2); merge(n2, n1); i++; } } return cost; } void init(int n, int m){ for(int i = 0; i <= n; i++)par[i] = i; cost = 0; for(int i = 0; i <= m; i++){ arr[i].start = arr[i].end = arr[i].weight = 0; } } int main(){ while(scanf("%d%d", &n, &m) && n && m){ long long total = 0; init(n, m); for(int i = 0; i < m; i++){ scanf("%d%d%d", &arr[i].start, &arr[i].end, &arr[i].weight); total += arr[i].weight; } printf("%lld\n", total-func()); } } /* 4 5 0 1 4 1 3 5 3 2 1 0 2 2 0 3 7 7 11 0 1 7 0 3 5 1 2 8 1 3 9 1 4 7 2 4 5 3 4 15 3 5 6 4 5 8 4 6 9 5 6 11 */
Sicily 7766:Dark roads(最小生成树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。