E - QS Network——最小生成树_Prim算法

骑猪看日落 2022-06-11 00:13 126阅读 0赞

Think:  
1知识点：最小生成树\_Prim算法  
2题意分析：n个结点，连接后信息可传递，边权等于两个结点的“适配器费用”加上“电缆费用”，询问最少花费；由连接后信息可传递可得到连接后的图应为连通图，进而考虑选择n-1条边连接n个结点即可

[vjudge题目链接][vjudge]

以下为Accepted代码—40ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    int e[1014][1014], vis[1014], dis[1014], book[1014];
    
    void Prim(int n);
    
    int main(){
        int T, n, i, j;
        scanf("%d", &T);
        while(T--){
            scanf("%d", &n);
            for(i = 1; i <= n; i++)
                scanf("%d", &book[i]);
            for(i = 1; i <= n; i++){
                for(j = 1; j <= n; j++){
                    scanf("%d", &e[i][j]);
                    if(i != j)
                        e[i][j] = e[i][j] + book[i] + book[j];
                }
            }
            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/E