最小生成树（无向图）
Kruskal
给所有边按从小到大排序 形成环则不选择（利用并查集）
P1546 最短网络 https://www.luogu.com.cn/problem/P1546
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std; struct Node {
int x, y, w;
friend bool operator < (const Node& a, const Node& b) {
return a.w < b.w;
}
}; Node a[];
int pre[]; int Find(int x) {
return pre[x] == x ? x : pre[x] = Find(pre[x]);
} int main() {
int n, k, cnt = ;
scanf("%d", &n);
for (int i = ; i < n; i++) {
pre[i] = i;
for(int j=;j<n;j++){
scanf("%d", &k);
if (j > i) { //矩阵只需判断一半
a[cnt].x = i;
a[cnt].y = j;
a[cnt++].w = k;
}
}
}
sort(a, a + cnt);
int ans = ;
int p = ;
for (int i = ; i <cnt; i++) {
if (Find(a[i].x) != Find(a[i].y)) {
ans += a[i].w;
pre[Find(a[i].x)] = a[i].y;
p++;
if (p == n - ) break;
}
}
printf("%d\n", ans);
return ;
}
HDU 1875 http://acm.hdu.edu.cn/showproblem.php?pid=1875
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
typedef long long ll;
using namespace std; struct Node {
int x, y;
double w;
friend bool operator < (const Node& a, const Node& b) {
return a.w < b.w;
}
}; Node a[]; //数组注意开大
int pre[];
double x[];
double y[]; int Find(int x) {
return pre[x] == x ? x : pre[x] = Find(pre[x]);
} double dis(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
int main() {
int T,c;
scanf("%d", &T);
while (T--) {
int cnt = ;
scanf("%d", &c);
for (int i = ; i < c; i++) {
pre[i] = i;
scanf("%lf%lf", &x[i], &y[i]);
for (int j = ; j < i; j++) {
double dist = dis(x[i], y[i], x[j], y[j]);
if(dist>=10.0&&dist<=1000.0){
a[cnt].x = i;
a[cnt].y = j;
//printf("%d %d\n", a[cnt].x, a[cnt].y);
a[cnt++].w = dist;}
}
}
sort(a, a + cnt);
double ans = ;
int p = ;
for (int i = ; i < cnt; i++) {
if (Find(a[i].x) != Find(a[i].y)) {
ans += a[i].w ;
pre[Find(a[i].x)] = a[i].y;
p++;
if (p == c - ) break;
}
}
if (p == c - ) printf("%.1f\n", ans*);
else printf("oh!\n");
}
return ;
}