pat顶级1024 Currency Exchange Centers （35 point(s)）

欢迎访问我的pat顶级题解目录哦 https://blog.csdn.net/richenyunqi/article/details/86751676

题目描述

算法设计

这是一道典型的求解最小生成树的问题，直接用Kruskal算法计算即可。唯一需要注意的就是如果有多棵最小生成树，需要选择一棵centers数量最小的树，这一点可以通过以下方法解决：

1. 定义一个unordered_set<string>set_centers存储已选中的边的center
2. 在边类的定义中，重载小于运算符时。当两个边的费用相等，则center已在set_centers中存在的边优先级更高

具体实现可见代码。

C++代码

#include<bits/stdc++.h>
using namespace std;
unordered_set<string>set_centers;//存储已选中的边的center
struct Edge{//边类int c1,c2,fee;string center;Edge(int cc1,int cc2,string cen,int f):c1(cc1),c2(cc2),center(cen),fee(f) {}