算法提高课汇总

算法思路

题目要求我们首先要选择若干顶点, 再从这些顶点出发向外延伸构建最小生成树. 一种思路是枚举所有起点,
在庞大的时间复杂度让我们打退堂鼓的时候, 回忆起AcWing 1137. 选择最佳线路解决有限起点或有限终点
的思路: 建立虚拟源点$s$, $w(s,i) = v_i$, 也就是虚拟源点到任意顶点$i$的权重等于在顶点$i$建立发电站的费用.

此时问题转化为经典的最小生成树问题, 此时的起点并非任意, 而是虚拟源点$s$.

具体实现

#include <cstring>
#include <iostream>

using namespace std;

const int N = 310;

int n;
int w[N][N];
int dist[N]; bool st[N]; //prim

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

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

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

        for( int v = 1; v <= n; v ++ )
            dist[v] = min( dist[v], w[u][v] );
    }
    return res;
}

int main()
{
    cin >> n;
    for( int i = 1; i <= n; i ++ )
    {
        cin >> w[0][i]; //以0作为虚拟源点 w(0, i) = v(i)
        w[i][0] = w[0][i];
    }
    for( int i = 1; i <= n; i ++ )
        for( int j = 1; j <= n; j ++ )
            cin >> w[i][j];

    cout << prim() << endl;

    return 0;
}