题目描述

建立一个超级发电站，使每个点距超级发电站的边权为vi，在此基础上求最小生成树，使整个图连通

prim要点：最外层循环i为点的个数，j为点的标号（次数也为点的个数），如果j没在集合中，且满足(t==-1 || (dist[j]<dist[t])) 才更新t，最后重新遍历一遍0到n号点，更新距离

#include <iostream>
#include <cstring>

using namespace std;

const int N=310;

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


int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res=0;
    dist[1]=0;
    for(int i=0;i<=n;i++)
    {
        int t=-1;
        for(int j=0;j<=n;j++)
        {
            if(!st[j] && (t==-1 || (dist[j]<dist[t])))
            {
                t=j;
            }
        }
        st[t]=1;
        res += dist[t];
        for(int j=0;j<=n;j++)
        {
            dist[j]=min(dist[j],w[t][j]);
        }
    }
    return res;
}

int main()
{
    cin>>n;
    //超级发电站设为0，输入每个点到超级发电站的距离
    for(int i=1;i<=n;i++)
    {
        cin>>w[0][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];
        }
    }
    int res=prim();
    cout<<res;

    return 0;
}

二刷，无向图，注意更新g[i][0]

#include <iostream>
#include <cstring>

using namespace std;

const int N=310;
int g[N][N];
int p[N];
int n;
int res;
int st[N];
int dist[N];

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

}

int main()
{
    cin>>n;

    //虚拟原点0
    for(int i=1;i<=n;i++)
    {
        cin>>g[0][i];
        g[i][0]=g[0][i];
    }

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

    cout<<prim();

    return 0;
}

三刷，多起点最小生成树，虚拟原点

处理多起点的经典办法为虚拟原点

#include <iostream>
#include <cstring>

using namespace std;

const int N=1010;
int dist[N],g[N][N];
int n;
int st[N];

int prim()
{
    int res=0;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    for(int i=0;i<=n;i++)
    {
        int t=-1;
        for(int j=0;j<=n;j++)
        {
            if((!st[j]) && (t==-1 || dist[t]>dist[j]))
            {
                t=j;
            }
        }

        if(st[t]) continue;
        st[t]=1;

        res+=dist[t];

        for(int j=0;j<=n;j++)
        {
            dist[j]=min(dist[j],g[t][j]);
        }
    }
    return res;

}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>g[0][i];
        g[i][0]=g[0][i];
    }

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

    return 0;
}

2023/12/22

多起点的最小生成树
思路是要有一个虚拟原点，记录这个原点到其他所有点的距离为g[0] [i]
然后在所有0-n的点中，做最小生成树

#include <iostream>
#include <cstring>

using namespace std;

const int N=310;

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


int main()
{
    cin>>n;
    memset(dist, 0x3f, sizeof(dist));
    for(int i=1;i<=n;i++)
    {
        cin>>g[0][i];
    }

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

    // 初始化虚拟原点的距离
    dist[0] = 0;
    int res = 0;
    for(int i=0;i<=n;i++)
    {
        int t = -1;
        for(int j=0;j<=n;j++)
        {
            if(!st[j] && (t== -1 || dist[t]>dist[j]))
            {
                t = j;
            }
        }

        st[t] = 1;
        res += dist[t];

        for(int j=0;j<=n;j++)
        {
            if(dist[j] > g[t][j])
            {
                dist[j] = g[t][j];
            }
        }
    }

    cout<<res;

    return 0;
}