洛谷题单 <最小生成树> building roads
洛谷题单<最小生成树> 2
krukal 的应用 题目告诉原有M条边 即修改M次并查集;考察对kruskal并查集的理解。
代码如下
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1010, M = 1010; struct edge{ int a, b; double c; bool operator<(const edge& w){ return c < w.c; } }edges[N*N];//完全图 边数位N^2级别 int n, m, p[N], cnt; long long px[N], py[N]; double get_len(int i,int j){ long long x = (ll)(px[i] - px[j]) * (px[i] - px[j]); long long y = (ll)(py[i] - py[j]) * (py[i] - py[j]); return sqrt(x + y); } int find(int x){ if(x != p[x]) return p[x] = find(p[x]); else return x; } double kruskal(int cnt){ sort(edges, edges + cnt); double res = 0; for(int i = 0;i < cnt; i++){ int a = edges[i].a, b = edges[i].b; double c = edges[i].c; int x = find(a), y = find(b); if(x != y){ p[x] = y; res += c; } } return res; } int main(){ cin >> n >> m; for(int i = 0; i <= n; i++) p[i] = i; for(int i = 1; i <= n; i ++){ int a, b; scanf("%d%d", &a, &b); px[i] = a, py[i] = b; } for(int i = 0; i < m; i++){ int a, b; scanf("%d%d", &a, &b); int x = find(a), y = find(b); if(x != y) p[x] = y; } int cnt = 0; for(int i = 1; i <= n; i++){ //建立完全图的边 for(int j = i + 1; j <= n; j++){ double z = get_len(i, j); edges[cnt ++] = {i, j, z}; } } double ans = kruskal(cnt); // 传入参数 :边数 printf("%.2f", ans); return 0; }