OpenJuege 兔子与星空

总时间限制:: 1000ms
内存限制:: 10000kB

描述

很久很久以前，森林里住着一群兔子。兔子们无聊的时候就喜欢研究星座。如图所示，天空中已经有了n颗星星，其中有些星星有边相连。兔子们希望删除掉一些边，然后使得保留下的边仍能是n颗星星连通。他们希望计算，保留的边的权值之和最小是多少？

OpenJuege 兔子与星空

输入

第一行只包含一个表示星星个数的数n，n不大于26，并且这n个星星是由大写字母表里的前n个字母表示。接下来的n-1行是由字母表的前n-1个字母开头。最后一个星星表示的字母不用输入。对于每一行，以每个星星表示的字母开头，然后后面跟着一个数字，表示有多少条边可以从这个星星到后面字母表中的星星。如果k是大于0，表示该行后面会表示k条边的k个数据。每条边的数据是由表示连接到另一端星星的字母和该边的权值组成。权值是正整数的并且小于100。该行的所有数据字段分隔单一空白。该星星网络将始终连接所有的星星。该星星网络将永远不会超过75条边。没有任何一个星星会有超过15条的边连接到其他星星（之前或之后的字母）。在下面的示例输入，数据是与上面的图相一致的。

输出

输出是一个整数，表示最小的权值和

 1 #include <iostream>
 2 #include <cstring>
 3 #include <queue>
 4 #define pause system("pause");
 5 using namespace std;
 6 
 7 struct Edge
 8 {
 9     int w;
10     int from, to;
11     Edge(int u, int v, int w) :
12         from(u), to(v), w(w) {}
13 };
14 
15 bool operator < (const Edge &E1, const Edge &E2)
16 {
17     return E1.w > E2.w;
18 }
19 
20 priority_queue<Edge> G;
21 int parent[100];
22 
23 int find(int x)
24 {
25     if (parent[x] < 0)
26         return x;
27     parent[x] = find(parent[x]);
28     return parent[x];
29 }
30 
31 bool merge(int u, int v)
32 {
33     int ru = find(u);
34     int rv = find(v);
35     if (ru != rv) {
36         parent[rv] = ru;
37         return true;
38     }
39     return false;
40 }
41 
42 int kruscal()
43 {
44     int ans = 0;
45     memset(parent, -1, sizeof(parent));
46     while (!G.empty()) {
47         Edge ep = G.top(); G.pop();
48         if (merge(ep.from, ep.to)) ans += ep.w;
49     }
50     return ans;
51 }
52 
53 int main()
54 {
55     int n;
56     cin >> n;
57     for (int i = 0; i < n - 1; i++) {
58         int edgeNum, weight;
59         char from, to;
60         cin >> from >> edgeNum;
61         while (edgeNum--) {
62             cin >> to >> weight;
63             if (from < to)
64                 G.push(Edge(from - 'A', to - 'A', weight));
65         }
66     }
67     cout << kruscal() << endl;
68     //pause;
69     return 0;
70 }

相关推荐