# HDU-1162 最小生成树(模板)
## [HDU-1162](http://acm.hdu.edu.cn/showproblem.php?pid=1162)
## 分析
一道最小生成树模板题, 不过处理边集时稍有变化: **每个点到每个点都可以有一条边**, 并且**每条边的权值就是两点间直线距离**.
使用**kruskal算法**求解.
### Kruskal算法
简单概括:
1. 构造边集
2. 排序边集, 权值小的优先
3. 遍历边集:
- 若此边两端属于同一分量, 则忽略此边.
- 否则, 将此边两端的分量合并, 此边作为桥. 并在此时进行其他处理(如统计花费, 构造生成树等)
这里对分量的操作可以转化为对节点的操作, 同一集合下的节点属于同一分量. 写得简单跑得快的方法当属**并查集**了
## 代码
```cpp
// -------------- GLOBAL ----------------
struct edge {
int u, v; // u和v存储点的序号
double dis; // 两点间的直线距离
};
vector<edge> edges;
double nodes[2][105]; // [x|y][i]
int setTree[105];
int n;
// -------------- FUNC ----------------
int find(int x) { return x == setTree[x] ? x : setTree[x] = find(setTree[x]); }
double kruskal() {
double sum = 0;
sort(stl(edges), [](const edge & e1, const edge & e2) {
return e1.dis < e2.dis;
});
FE(e, edges) {
int a = find(e.u), b = find(e.v);
if (a != b) {
setTree[a] = b; // 并 查 集
sum += e.dis;
}
}
return sum;
}
// -------------- MAIN ----------------
int main() {
ios_base::sync_with_stdio(false);
while (~INI(n)) {
edges.resize(0);
fill0(nodes);
F1(i, n) {
setTree[i] = i;
IND(nodes[0][i]);
IND(nodes[1][i]); // 点集
}
// 生成边集(任意两个点的组合)
for (int i = 1; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
double dis; // 求对角线距离
{
int x = nodes[0][i] - nodes[0][j];
int y = nodes[1][i] - nodes[1][j];
dis = sqrt(pow(x, 2) + pow(y, 2));
}
edges.push_back(edge{i, j, dis});
}
}
printf("%.2f\n", kruskal());
}
return 0;
}
```
![]()