算法提高课汇总

模型抽象

• $n$个顶点的无向图.

• 连接所有顶点 --> 联通

• 连接所有顶点的最小边权和 --> 最小生成树.

$Prim\;O(n^2)$

输入图的邻接矩阵, 用$prim$可以简单解决.

#include <cstring>
#include <iostream>

using namespace std;

const int N = 110;

int n;
int g[N][N];
int dist[N]; //dist[v]: 当前联通块S到v的最短距离
bool st[N]; //st[v]: 当前顶点v是否被加入联通块中

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

    int res = 0;
    for( int i = 1; i <= n; i ++ )
    {
        int u = -1;
        for( int v = 1; v <= n; v ++ )
        {
            if( !st[v] && (u == -1 || dist[u] > dist[v]) )
                u = v;
        }

        st[u] = true;
        res += dist[u];

        for( int v = 1; v <= n; v ++ )
            dist[v] = min( dist[v], g[u][v] );
    }
    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;
}