A - Jungle Roads——最小生成树

曾经终败给现在 2022-06-12 14:39 169阅读 0赞

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

[vjudge题目链接][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);
    }

[vjudge]: https://vjudge.net/contest/163010#problem/A