POJ 1251 Jungle Roads 九度 OJ1154 最小生成树问题 输入转换

题目链接

题目大意：
给你无向图中每条边的长度,要你求该图的最小生成树。其中每个顶点用大写字母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;
}