B - Networking——最小生成树_Prim算法(未堆优化)

旧城等待， 2022-06-12 14:43 100阅读 0赞

Think:  
1知识点：最小生成树\_Prim算法(未堆优化)  
2题意分析：  
1>n个点，选择最优方案连成一个网络，注:初始给定边无限  
2>即选择n-1条边将n个结点连通  
3>边无限即稠密图，进而选择最小生成树Prim算法(未堆优化)  
3反思：memset()初始化注意第三个参数应为sizeof(初始化数组)  
4思考：稠密图，Prim算法(未堆优化)

[vjudge题目链接][vjudge]

以下为Accepted代码  
1>16ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    int e[104][104], vis[104], dis[104];
    
    void Prim(int n);
    
    int main(){
        int n, m, u, v, w;
        while(scanf("%d", &n) && n){
            scanf("%d", &m);
    
            memset(e, inf, sizeof(e));
    
            while(m--){
                scanf("%d %d %d", &u, &v, &w);
                if(e[u][v] > w)
                    e[u][v] = e[v][u] = w;
            }
    
            Prim(n);
        }
        return 0;
    }
    void Prim(int n){
        int i, miv, v, 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/B