A - Jungle Roads——最小生成树-蒲公英云

A - Jungle Roads——最小生成树

Think:
1知识点：最小生成树
2题意分析：n个村庄选择可以将n个村庄连通的n-1条路进行维护，询问最小维护费用，即n个结点选择n-1条边建立最小生成树
3反思：Prim()算法注意结点记录变量初始化应为1,以及地图信息记录数组初始化应为inf(0x3f3f3f3f)——当前题目
4思考：Kruskal算法适用于稀疏图时间复杂度m+nlg(n),未堆优化的Prim算法适用于稠密图时间复杂度n^2

vjudge题目链接

以下为Accepted代码——Kruskal算法

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Edge{
    int u, v, w;
    bool operator < (const Edge &b) const{
        return w < b.w;
    }
}link[2014];
int tp, f[40];
void add_edge(int u, int v, int w);
void Init(int n);
int get_f(int x);
bool Merge(int x, int y);
void Kruskal(int n);
int main(){
    int n, i, k, u, v, w;
    char st[14];
    while(~scanf("%d", &n) && n){
        tp = 0;
        for(i = 1; i < n; i++){
            scanf("%s %d", st, &k);
            u = st[0] - 'A' + 1;
            while(k--){
                scanf("%s %d", st, &w);
                v = st[0] - 'A' + 1;
                add_edge(u, v, w);
            }
        }
        Kruskal(n);
    }
    return 0;
}
void add_edge(int u, int v, int w){
    link[tp].u = u;
    link[tp].v = v;
    link[tp].w = w;
    tp++;
}
void Kruskal(int n){
    Init(n);
    sort(link, link+tp);
    int cnt = 0, sum = 0;
    for(int i = 0; i < tp; i++){
        int x = link[i].u;
        int y = link[i].v;
        if(Merge(x, y)){
            cnt++;
            sum += link[i].w;
            if(cnt == n-1)
                break;
        }
    }
    printf("%d\n", sum);
}
void Init(int n){
    for(int i = 0; i <= n; i++)
        f[i] = i;
}
int get_f(int x){
    if(f[x] == x)
        return x;
    return f[x] = get_f(f[x]);
}
bool Merge(int x, int y){
    int t1 = get_f(x);
    int t2 = get_f(y);
    if(t1 == t2)
        return false;
    else {
        f[t2] = t1;
        return true;
    }
}

以下为Accepted代码——Prim算法

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
int e[42][42], dis[42], vis[42];
void Prim(int n);
int main(){
    int n, i, k, u, v, w;
    char st1[14], st2[14];
    while(scanf("%d", &n) && n){
        getchar();
        memset(e, inf, sizeof(e));
        for(i = 1; i < n; i++){
            scanf("%s %d", st1, &k);
            u = st1[0]-'A'+1;
            while(k--){
                scanf("%s %d", st2, &w);
                v = st2[0]-'A'+1;
                e[u][v] = e[v][u] = w;
            }
        }
        Prim(n);
    }
    return 0;
}
void Prim(int n){
    int i, v, miv, num, sum;
    memset(vis, 0, sizeof(vis));
    for(i = 1; i <= n; i++)
        dis[i] = e[1][i];
    vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
    while(num < n){
        miv = inf;
        for(i = 1; i <= n; i++){
            if(!vis[i] && dis[i] < miv){
                miv = dis[i], v = i;
            }
        }
        vis[v] = 1, num++, sum += dis[v];
        for(i = 1; i <= n; i++){
            if(!vis[i] && e[v][i] < dis[i])
                dis[i] = e[v][i];
        }
    }
    printf("%d\n", sum);
}