PTA 7-11 公路村村通

PTA 7-11 公路村村通

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

#include #include #include #include using namespace std;const int maxn = 1010;struct Edge { int from, to, cost; bool operator < (const Edge &e) const { return cost < e.cost; }}edge[maxn * 3];int par[maxn];int query(int x) { return par[x] == x ? x : par[x] = query(par[x]); }int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i <= n; i++) par[i] = i; for (int i = 1; i <= m; i++) scanf("%d %d %d", &edge[i].from, &edge[i].to, &edge[i].cost); sort(edge + 1, edge + 1 + m); int cnt = 0, ans = 0; for (int i = 1; i <= m && cnt <= n - 1; i++) { int u = edge[i].from, v = edge[i].to, cost = edge[i].cost; u = query(u), v = query(v); if (u == v) continue; par[u] = v; ans += cost; cnt++; } if (cnt == n - 1) printf("%d\n", ans); else printf("-1\n"); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。