- 1#include 2#include 3 using namespace std;
- 4 5 struct TnT {
- 6 int x1;
- 7 int x2;
- 8 int val;
- 9
- }
- T[1111];
- 10 11 int Father[30];
- 12 char arr[27] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
- 13 14 int find(int x) {
- return x == Father[x] ? x: Father[x] = find(Father[x]);
- }
- 15 16 void Union(int x, int y) {
- 17 int fx = find(x),
- fy = find(y);
- 18
- if (fx != fy) Father[fx] = fy;
- 19
- }
- 20 21 bool cmp(TnT a, TnT b) {
- 22
- return a.val < b.val;
- 23
- }
- 24 25 int renum(char m) {
- 26
- for (int i = 0; i < 26; i++) {
- 27
- if (m == arr[i]) 28
- return i + 1;
- 29
- }
- 30
- }
- 31 32 int main() {
- 33 int n,
- l,
- r,
- cnt;
- 34 char m;
- 35
- while (cin >> n && n != 0) {
- 36 int t = 0,
- sum = 0;
- 37
- for (int i = 1; i <= n; i++) Father[i] = i;
- 38
- for (int i = 1; i) {
- 39 cin >> m >> cnt;
- 40 l = renum(m);
- 41
- for (int i = 0; i) {
- 42 cin >> m >> T[t].val;
- 43 r = renum(m);
- 44 T[t].x1 = l,
- T[t].x2 = r;
- 45 t++;
- 46
- }
- 47
- }
- 48 sort(T, T + t, cmp);
- 49
- for (int i = 0; i) {
- 50
- if (find(T[i].x1) != find(T[i].x2)) {
- 51 Union(T[i].x1, T[i].x2);
- 52 sum += T[i].val;
- 53
- }
- 54
- }
- 55 cout < endl;
- 56
- }
- 57
- return 0;
- 58
- }
来源: http://www.bubuko.com/infodetail-2003533.html