求图的最小生成树的权值

邻接表方法

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
typedef struct Enode* Arc;
const int INF=0x3f3f3f3f;
struct Enode
{
    int vex;
    int w;
    Arc next;
};
struct Vnode
{
    bool flag;
    Arc ed;
    Vnode():flag(false),ed(NULL){}
};
struct Vnode Ge[505];
void createGraph(int);
void Add_e(int,Arc);
void Prim(int,int);
int main()
{
    int n,m;
    cin>>n>>m;
    createGraph(m);
    Prim(n,m);
    return 0;
}
void createGraph(int m)
{
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        Arc newnode=new Enode;
        newnode->next=NULL;
        newnode->vex=v;newnode->w=w;
        Add_e(u,newnode);
        Arc n2=new Enode;
        n2->next=NULL;n2->vex=u;n2->w=w;
        Add_e(v,n2);
    }
}
void Add_e(int u,Arc newnode)
{
    if(Ge[u].ed==NULL)
    {
        Ge[u].ed=newnode;
    }
    else
    {
        Arc cur=Ge[u].ed;
        Arc temp=cur->next;
        while(temp!=NULL)
        {
            cur=temp;
            temp=temp->next;
        }
        cur->next=newnode;
    }
}
void Prim(int n,int m)
{
    bool visited[505];
    int minDist[505];
    for (int i = 1; i <= n; ++i) {
        visited[i] = false;
        minDist[i] = INF;
    }

    minDist[1] = 0;
    int sumWeight = 0;

    for (int i = 1; i <= n; ++i) {
        int minWeight = INF;
        int u = -1;
        for (int j = 1; j <= n; ++j) {
            if (!visited[j] && minDist[j] < minWeight) {
                minWeight = minDist[j];
                u = j;
            }
        }

        if (u == -1) {
            cout << "impossible" << endl;
            return;  // 无法构成最小生成树
        }

        visited[u] = true;
        sumWeight += minWeight;

        for (Arc e = Ge[u].ed; e != NULL; e = e->next) {
            int v = e->vex;
            int w = e->w;
            if (!visited[v] && w < minDist[v]) {
                minDist[v] = w;
            }
        }
    }
    cout << sumWeight << endl;
}

邻接矩阵方法

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
const int N=505,M=100005,INF=0x3f3f3f3f;
int n,m;
int g[N][N];//邻接矩阵复杂度太高建议用邻接表
bool st[N];

int Prim()
{
    priority_queue<PII,vector<PII>,greater<PII>> q;
    long long res=0;
    q.push({0,1});
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int a=t.second;
        if(st[a])continue;
        st[a]=true;
        res+=t.first;
        for(int i=1;i<=n;i++)
        {
            int w=g[a][i];
            if(w<INF)
            {
                q.push({w,i});
            }
        }
    }
    for(int i=1;i<=n;i++)if(!st[i])return -1;
    return res;
}
int main()
{
    memset(g,0x3f,sizeof g);
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        g[u][v]=g[v][u]=min(g[u][v],w);
    }
    long long res=Prim();
    if(res==-1)puts("impossible");
    else printf("%lld\n",res);
    return 0;
}