最小生成树

定义 : 对于图 $ G = (V,E) $, 有 $n$ 个点, $m$ 条边, 由 $V$ 中所有 $n$ 个点和 $E$ 中 $n-1$ 条边构成的一个连通子图(即一棵树),称为 $G$ 的一个生成树, 边权值最小的为最小生成树.

求解方法:

1. prim算法 $O(n^2)$
2. kruskal算法 $O(mlogn)$

prim算法 :

一般用于稠密图:

#include <iostream>
#include <cstring>

using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 510;
int n,m;
int g[N][N];    //稠密图
int dist[N];    //表示某个结点到当前集合的最小距离(与dijkstra不同)
int st[N];      //是否在集合内

int prim()
{
    memset(dist, INF, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ ){

        int t = -1; 
        for (int j = 1; j <= n; j ++ )          //寻找不在集合内，且到集合距离最小的结点
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;      //进入集合

        if (i && dist[t] == INF)    return INF; //不存在生成树
        if (i)  res += dist[t];

        for (int j = 1; j <= n; j ++ )      //更新其它结点
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n >> m;

    memset(g, INF, sizeof g);

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        g[a][b] = g[b][a] = min(g[a][b], v);    //无向图
    }

    int t = prim();

    if (t == INF)
        puts("impossible");
    else    
        cout << t << endl;

    return 0;
}

kruskal算法 :

一般用于稀疏图

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
const int M = 2 * N;
int n,m;

int f[N];       //并查集的操作

struct Edge{
    int a, b;
    int v;
}edge[M];

bool comp(Edge x, Edge y)       //自定义比较
{
    return x.v < y.v;
}

int find(int x)                 //寻找祖宗结点
{
    if (f[x] != x)  return f[x] = find(f[x]);
    return f[x];
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1, comp);

    for (int i = 1; i <= n; i ++ )      //并查集的初始化
        f[i] = i;

    int res = 0;        //记录距离之和
    int cnt = 0;        //存储结点数量
    for (int i = 1; i <= m; i ++ ){      //枚举每条边

        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int fa = find(a);
        int fb = find(b);

        if (fa != fb){           //合并集合
            f[fa] = fb;
            res += v;
            cnt ++;
        }
    }
    if (cnt < n - 1)
        puts("impossible");
    else
        cout << res << endl;

    return 0;

}

AcWing 1140. 最短网络 原题链接

算法思路:

最小生成树的模板题, 输入矩阵形式, 采用prim算法

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110;

int g[N][N];
int n;
int dist[N];
int st[N];

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    int res = 0;

    for (int i = 1; i <= n; i ++ ){
        int t = -1;

        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        st[t] = 1;

        res += dist[t];

        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            cin >> g[i][j];

    cout << prim() << endl;

    return 0;
}

AcWing 1141. 局域网 原题链接

算法思路 :

kruakal算法求最小生成树, 注意每次当两个点需要删边时, 将结果加上权值.

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 220;

struct Edge{
    int a, b, v;

    bool operator < (const Edge &t)const 
    {
        return v < t.v;
    }
}edge[M];
int fa[N];
int n ,m;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}


int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= m; i ++ )
        cout << edge[i].v << endl;
    for (int i = 1; i <= m; i ++ ){
        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int aa = find(a);
        int bb = find(b);

        if (aa != bb)   fa[aa] = bb;
        else
            res += v;
    }

    cout << res << endl;

    return 0;
}

AcWing 1142. 繁忙的都市 原题链接

算法思路 :

同样是模板题, 注意理解题意, 要求被改造的道路能够连通整个图(被选入生成树里的点)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310, M = 8010;

struct Edge{
    int a, b, v;
    bool operator < (const Edge &t)const
    {
        return v < t.v;
    }
}edge[M];

int n,m;
int fa[N];
int sum;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}


int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= m; i ++ ){
        int a, b, v;
        cin >> a >> b >> v;
        edge[i] = {a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int a = edge[i].a;
        int b = edge[i].b;
        int v = edge[i].v;

        int aa = find(a);
        int bb = find(b);
        //cout << aa << ' ' << bb << endl;
        if (aa == bb)
            continue;
        else{
            sum ++;
            fa[aa] = bb;
            res = v;

        }
    }

    cout << sum << ' ' << res << endl;

    return 0;

}

AcWing 1143. 联络员 原题链接

算法思路 :

图中含有必选边和非必选边, 对于必选边我们直接加入到生成树中, 然后再根据kruskal算法加入非必选边

• kruskal算法求最小生成树可以从中间开始

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010, M = 10010;

struct Edge{
    int op, a, b, v;
    bool operator < (const Edge &t)const
    {
        if (op == t.op)
            return v < t.v;
        return op < t.op;
    }
}edge[M];
int fa[N];
int n, m;


int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    else
        return x;
}

int main()
{
    cin >> n >> m;
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        fa[i] = i;

    for (int i = 1; i <= m; i ++ ){
        int op, a, b, v;
        cin >> op >> a >> b >> v;
        edge[i] = {op, a, b, v};
    }

    sort(edge + 1, edge + m + 1);

    for (int i = 1; i <= m; i ++ ){
        int op = edge[i].op;
        int aa = find(edge[i].a);
        int bb = find(edge[i].b);
        int v = edge[i].v;

        if (op == 1){
            res += v;
            if (aa != bb)
                fa[aa] = bb;
        }else{
            if (aa == bb)
                continue;
            else{
                res += v;
                fa[aa] = bb;
            }
        }
    }


    cout << res << endl;

    return 0;
}

AcWing 1144. 连接格点 原题链接

算法思路 :

原图中有 $m * n$ 个点, 其中横向点之间、纵向点之间都有边, 根据kruskal算法,先加入纵向边(权值小),再加入横向边(权值大).
我们可以直接在加边时进行排序,避免sort().

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2 * 1e6 + 10, M = 2 * 1e6 + 10;
int g[1010][1010];
struct Edge{
    int a, b, v;

    bool operator < (const Edge &t)const
    {
        return v < t.v;
    }
}edge[M];
int fa[N];
int n, m;

int find(int x)
{
    if (fa[x] != x)
        fa[x] = find(fa[x]);
    return fa[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1, t = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            g[i][j] = t ++;

    for (int i = 1; i <= n * m; i ++ )
        fa[i] = i;

    int cnt = 0;
    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j < n; j ++ ){
            int a = g[j][i], b = g[j + 1][i];
            int v = 1;
            //cout << a << ' ' << b << endl;
            edge[cnt ++] = {a, b, v};
        }

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j < m; j ++ ){
            int a = g[i][j], b = g[i][j + 1];
            int v = 2;
            //cout << a << ' ' << b << endl;
            edge[cnt ++] = {a,b,v};
        }
    int x1, y1, x2, y2;
    while (~scanf("%d%d%d%d",&x1, &y1, &x2, &y2)){
        int a = g[x1][y1];
        int b = g[x2][y2];
        int aa = find(a);
        int bb = find(b);
        fa[aa] = bb;
    }

    int res = 0;

    for (int i = 0; i < cnt; i ++ ){
        int aa = find(edge[i].a);
        int bb = find(edge[i].b);
        int v = edge[i].v;
        if (aa == bb)
            continue;
        else{
            res += v;
            fa[aa] = bb;
        }
    }

    cout << res << endl;

    return 0;

}