首页 > 代码库 > hdu1863 畅通工程 基础最小生成树
hdu1863 畅通工程 基础最小生成树
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #define N 110 5 #define M 5000 6 using namespace std; 7 8 int n, m, u[M], v[M], w[M], r[M], p[N]; 9 bool cmp(int i, int j){ return w[i]<w[j]; } 10 int f(int x){ return p[x] == x ? x : p[x] = f(p[x]); } 11 12 int main() 13 { 14 while (cin >> m >> n&&m) 15 { 16 for (int i = 1; i <= n; ++i) p[i] = i; 17 for (int j = 1; j <= m; ++j) r[j] = j; 18 for (int j = 1; j <= m; ++j) cin >> u[j] >> v[j] >> w[j]; 19 sort(r + 1, r + 1 + m, cmp); 20 int ans = 0, k = 0; 21 for (int j = 1; j <= m&&k<n - 1; ++j) 22 { 23 int e = r[j]; int x = f(u[e]), y = f(v[e]); 24 if (x != y)ans += w[e], ++k, p[x] = y; 25 } 26 if (k<n - 1)puts("?"); 27 else cout << ans << endl; 28 } 29 return 0; 30 }
hdu1863 畅通工程 基础最小生成树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。