```#include <iostream>
#include <queue>
using namespace std;

typedef struct node{
int start;
int end;
int len;
}Edge;

struct cmp{
bool operator() (Edge e1,Edge e2){
return e1.len>e2.len;
}
};

const int MAX = 5000;
int data[MAX];
int N,start,end,len,n,sum;
char ch;
priority_queue<Edge,vector<Edge>,cmp> Q;

int Find(int root)
{
if(data[root] < 0){
return root;
}
return data[root] = Find(data[root]);
}

void Union(int root1 ,int root2)
{
root1 = Find(root1);
root2 = Find(root2);
if(root1 == root2){
return;
}else if(root1 < root2){
data[root1] += data[root2];
data[root2] = root1;
}else{
data[root2] += data[root1];
data[root1] = root2;
}
N--;
}

int Kruskal()
{
int sum = 0;
while(!Q.empty()){
Edge e = Q.top();
Q.pop();
int root1 = e.start;
int root2 = e.end;
if(Find(root1) != Find(root2)){
sum += e.len;
Union(root1,root2);
}
if(N == 1){
break;
}
}
return sum;
}

int main()
{
while(cin>>N){
if(N == 0){
break;
}
while(!Q.empty()){
Q.pop();
}
for(int i = 0 ; i < MAX ; i++){
data[i] = -1;
}
for(int i = 1 ; i < N ; i++){
cin>>ch>>n;
start = ch-'A'+1;
if(n > 0){
for(int j = 0 ; j < n ; j++){
cin>>ch>>len;
end = ch-'A'+1;
Edge e;
e.start = start;
e.end = end;
e.len = len;
Q.push(e);
}
}
}
sum = Kruskal();
cout<<sum<<endl;
}

return 0;
}```

0 条评论

• ### 09-排序2 Insert or Merge (25分)

Insertion sort iterates, consuming one input element each repetition, and growin...

• ### 11-散列2 Hashing (25分)

The task of this problem is simple: insert a sequence of distinct positive integ...

• ### 九度OJ——1144Freckles

题目描述： In an episode of the Dick Van Dyke show, little Richie connects the ...

• ### 11-散列2 Hashing (25分)

The task of this problem is simple: insert a sequence of distinct positive integ...

• ### HDU 4247 Pinball Game 3D(cdq 分治+树状数组+动态规划)

Pinball Game 3D Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/...

• ### 实验2 C++数组与指针

ASM是Java中比较流行的用来读写字节码的类库，用来基于字节码层面对代码进行分析和转换。

• ### 阶乘很简单？恕我直言，阶乘相关的面试题你还真不一定懂！

对于如何算 n 的阶乘，只要你知道阶乘的定义，我想你都知道怎么算，但如果在面试中，面试官抛给你一道与阶乘相关，看似简单的算法题，你还真不一定能够给出优雅的答案！...

• ### HDU 5421 Victor and String（回文树）

Victor and String Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 52428...

### 活动推荐 