prim-acwing

题目：Prim算法求最小生成树

858. Prim算法求最小生成树 - AcWing题库

代码：（邻接矩阵+dt数组存最短路写法）

感觉跟最短路径是一样的，只是多了个最小生成树概念

dt 存的其实是， 编号 + 权值， 例如 边 a --5-- b  , 其实是dt[b] = 5;

刚开始选生成树入口 ： dt[1] = 0,  其实就是 --0-- 1 .

#include<bits/stdc++.h>
using namespace std;

const int N = 510;
int g[N][N];
int st[N], dt[N], pre[N]; // 标记，最短距离，前驱
// pre 的作用
int n, m;

void prim() {
    int res = 0;
    dt[1] = 0; // 从编号1开始生成 树
    // 选n次编号结点
    for(int i = 0; i < n; i ++) {
        // 选最短路径编号
        int t = -1;
        for(int j = 1; j <= n; j ++ ) {
            if(!st[j] && (t==-1 || dt[t] > dt[j]))
                t = j;
        }
        // 最小生成树不存在，出现 不连通 的情况，还没有选完n次，就已经出现无穷路径。
        if(dt[t] == 0x3f3f3f3f) {
            cout << "impossible" << endl;
            return ;
        }
        st[t] = 1; //加入生成树
        res += dt[t]; //代价
        // 更新其他点到生成树的路径, 
        for(int k = 1; k <= n; k ++) 
            if(!st[k] && dt[k] > g[t][k]) {
                dt[k] = g[t][k];
                pre[k] = t; // 更新前驱
            }
    }
    cout << res << endl;
}
// 该题用不上，当作模板
void Printpath() {
    for(int i = n; i > 1; i --) { // 除去编号1
        cout << i << " " << pre[i] << " " << endl; // 边： 结点 前驱结点
    }
}

int main() {
    
    memset(g,0x3f,sizeof g);
    memset(dt,0x3f,sizeof dt);
    
    cin >> n >> m;
    while(m --) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = g[b][a] = min(g[a][b],w); // min(是因为可能会有重边，选小的)一边多权值，选小的
    }
    
    prim();
    // Printpath() // 输出路径
    return 0;
}

代码2（邻接表+小根堆存最短路 ： 堆优化写法）

优化了遍历最短路编号的过程。

堆中存的是dt 的更新信息，要的是每次最小的。 也就是说， PII 依旧跟dt 概念一样：

a -- 5 -- b; dt[b] = 5.   <5,b> 距离放first 小根堆自动按距离排序。

#include<bits/stdc++.h>
using namespace std;

const int N = 510, M = 1e5+10;
using PII = pair<int,int>;

int n, m;
int h[N], e[M*2], ne[M*2], w[M*2], idx;
int dt[N], st[N];

void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

void prim() {
    priority_queue<PII,vector<PII>, greater<PII>> heap;
    
    int res = 0, ans = 0;
    dt[1] = 0; 
    heap.push({0,1}); // 树的入口
    
    while(heap.size()) {
        // 最短路径
        auto t = heap.top(); heap.pop();
        // 入树了的continue;
        if(st[t.second]) continue;
        st[t.second] = 1, ans ++;
        res += dt[t.second];
        
        for(int i = h[t.second]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dt[j] > w[i] && !st[j]) { // 未选点到生成树的距离
                dt[j] = w[i];
                heap.push({dt[j],j});
            }
        }
    }
    //cout << res << endl;
    if(ans == n) cout << res << endl;
    else cout << "impossible" << endl;
    
}

int main() {
    memset(dt,0x3f,sizeof dt);
    memset(h,-1,sizeof h);
    cin >> n >> m;
    while(m --) {
        int a, b, w;
        cin >> a >> b >> w;
        add(a,b,w); // 邻接表有重边
        add(b,a,w);
    }
    
    prim();
    
    return 0;
}