搜索与图论_最小生成树

最小生成树

prim算法

代码模板

int prim() {
    int ans = 0;
    memset(d, 0x3f, sizeof d);
    for(int i = 0; i < n; i++) {
        int t = -1;
        for(int j = 1; j <= n; j++) {
            if(!st[j] && (t == -1 || d[t] > d[j])) t = j;
        }
        if(i && d[t] == INF) return INF;
        if(i) ans += d[t];
        st[t] = true;
        for(int j = 1; j <= n; j++) {
            d[j] = min(d[j], g[t][j]);
        }
    }
    return ans;
}

Kruskal算法

代码模板

struct edge {
    int a, b, w;
    bool operator < (const edge & T) const {
        return w < T.w;
    }
}edges[M];

int getfa(int x) {
    return fa[x] = (fa[x] == x) ? x : getfa(fa[x]);
}

int kruskal() {
    sort(edges, edges + m);
    int ans = 0, cnt = 0;
    for(int i = 0; i < m; i++) {
        int a = edges[i].a, b =  edges[i].b, c = edges[i].w;
        a = getfa(a), b = getfa(b);
        if(a != b) {
            fa[a] = b;
            cnt++;
            ans += c;
        }
    }
    if(cnt < n - 1) return INF;
    return ans;
}