题目描述

prim模板题，直接套prim即可
因为是稠密图，用邻接矩阵存，所以选择prim算法

#include <iostream>
#include <cstring>

using namespace std;

const int N=110;

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


int prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    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;
            }
        }

        if(dist[t]==0x3f3f3f3f) return -1;

        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();
    return 0;
}

prim二刷，prim用在稠密图

#include <iostream>
#include <cstring>

using namespace std;

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

int prim()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    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[j]<dist[t]))
            {
                t=j;
            }
        }
        if(dist[t]==0x3f3f3f3f) return -1;
        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();


}

三刷，不看一眼板子还是想不起来怎么做，，这几天抓紧复习一下

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=10010;
typedef pair<int,int> pii;
int e[N],ne[N],h[N],w[N],st[N],idx;
int dist[N];
int g[N][N];
int 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]==0 && (t==-1 || (dist[j]<dist[t])))
            {
                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();
    return 0;
}

四刷，不看板子做出来了

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=1010;
int dist[N],g[N][N],st[N];
int 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[j]<dist[t]))
            {
                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();
    return 0;
}

2023/12/22

prim模板题
使用朴素djk求解

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

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

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

    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++)
        {
            if(dist[j] > g[t][j])
            {
                dist[j] = g[t][j];
            }
        }
    }


    cout<<res;

    return 0;
}