201412-4 ccf 最优灌溉（最小生成树）

电玩女神 2022-05-15 10:22 144阅读 0赞

题目链接：  
[最优灌溉][Link 1]

题目大意：  
中文题目，不解释23333

解题思路：  
根据题目要求，所有麦田都要被灌溉，且使花费最小，抽象出来就是求无向带权图的MST（即最小生成树）。  
由于点少边多，属于稠密图，选择prim()算法，复杂度为O(n^2),n为点数，另一个算法复杂度适合简单图，复杂度为O(e\*log(2e))，e为边数。

因此直接套prim算法板子就好了啊！！  
不过我自己用优先队列撸了一下prim算法，和模板不太一样，自我感觉自己的代码优雅一点，哈哈哈！！！

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <vector>
    #include <queue>
    
    
    using namespace std;
    
    const int INF = 0x3f3f3f3f;
    struct node{
        int v;
        int w;
        node(int _v, int _w):v(_v),w(_w){}
        bool operator <(const node &a)const{
            return w > a.w;
        }
    };
    
    vector<node> g[1005];
    int vis[1005];
    int n,m;
    
    int prim(){
        priority_queue<node> pq;
        for(int i=0; i<g[1].size(); ++i){
            pq.push(g[1][i]);
        }
        vis[1] = 1;
        int num = 0, ans = 0;
        while(!pq.empty()){
            node tmp = pq.top();
            pq.pop();
            int u = tmp.v;
            if(vis[u]) continue;  //如果已经访问过了，需要跳过，否则构成回路了
            vis[u] = 1;
            for(int j=0; j<g[u].size(); ++j){
                if(!vis[g[u][j].v]){  //将连接没有访问过的点的边加入优先队列
                    pq.push(g[u][j]);
                }
            }
            ans += tmp.w;
            num++;
            if(num==n-1) return ans; //n个点的图，n-1条边就是连通图，退出
        }
    }
    
    void init(){
        memset(vis, 0, sizeof(vis));
        for(int i=0; i<1005; ++i) g[i].clear();
    }
    
    int main(){
        init();
        cin>>n>>m;
        for(int i=0; i<m; ++i){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            g[u].push_back(node(v,w));
            g[v].push_back(node(u,w));
        }
        cout<<prim();
        return 0;
    }

[Link 1]: http://118.190.20.162/view.page?gpid=T18