题目链接
题目大意:
给你无向图中每条边的长度,要你求该图的最小生成树。其中每个顶点用大写字母A-Z表示。
解题思路:
最小生成树问题,这里使用的是Kruskal算法,注意转换输入格式。
笔记:scanf()函数输入的时候,%s比%c使用起来更加方便,因为%s不需要考虑空格和换行符的问题
AC代码:将scanf函数的输入全部换成注释掉的cin输入也可以AC
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
#define maxn 27
int tree[maxn];
int findroot(int x) {
if (tree[x] == -1)return x;int tmp = findroot(tree[x]);tree[x] = tmp;return tmp;
}
bool unit(int a, int b) {
int fa = findroot(a);int fb = findroot(b);if (fa != fb) {
tree[fa] = fb;return true;}return false;
}
struct E {
int from, to;int cost;bool operator < (const E &a) const {
return cost < a.cost;}
}edge[76];void init() {
for (int i = 0; i < maxn; i++) {
tree[i] = -1;}
}
int main() {
int n;//while (cin >> n && n) {
while (scanf("%d",&n)!=EOF && n) {
init();int cnt = 0;while (n - 1 > 0) {
char a[2], b[2]; int cost, m;//cin >> a >> m;scanf("%s %d ", a, &m);while (m--) {
//cin >> b >> cost;scanf("%s %d", b, &cost);edge[++cnt].from = a[0] - 'A';edge[cnt].to = b[0] - 'A';edge[cnt].cost = cost;}n--;}sort(edge + 1, edge + 1 + cnt);int ans = 0;for (int i = 1; i <= cnt; i++) {
if (unit(edge[i].from, edge[i].to)) {
ans += edge[i].cost;}}printf("%d\n", ans);}return 0;
}