洛谷p3366

#include <bits/stdc++.h>
using namespace std;

const int N = 5005, INF = 0x3f3f3f3f;

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

int prim()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st,false,sizeof st);
    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 (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}


int main()
{
    cin>>n>>m;
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        cin>>a>>b>>c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    int t = prim();
    if(t==INF)cout<<"orz"<<endl;
    else cout<<t<<endl;

    return 0;
}

#include<bits/stdc++.h>
using namespace std;

const int maxn=5005;
int n,m;
int ans=0;

typedef struct
{
    int lowcost;
    int adjvex;
}Element;

void Prim(int arc[maxn][maxn],int w)
{
    int i,j,k;
    int Min;
    Element shortEdge[n+1];
    for(i=1;i <= n;i++)
    {
        shortEdge[i].lowcost=arc[w][i];
        shortEdge[i].adjvex=w;
    }
    shortEdge[w].lowcost=0;
    for(i=1;i <= n-1;i++)
    {
        Min=0x3f3f3f3f;
        for(j=1;j <= n;j++)
        {
            if((shortEdge[j].lowcost!=0)&&(shortEdge[j].lowcost < Min))
            {
                Min=shortEdge[j].lowcost;
                k=j;
            }
        }
        ans+=shortEdge[k].lowcost;
        shortEdge[k].lowcost=0;
        for(j=1;j<= n;j++)
        {
            if(arc[k][j]< shortEdge[j].lowcost)
            {
                shortEdge[j].lowcost=arc[k][j];
                shortEdge[j].adjvex=k;
            }
        }
    }
}

int main()
{
    int arc[maxn][maxn];
    int a,b,c;
    ans=0;
    cin>>n>>m;
    memset(arc,0x3f3f3f3f,sizeof arc);
    for(int i=0;i<m;i++)
    {
        cin>>a>>b>>c;
        if(arc[a][b]>c)
        {
            arc[a][b]=c;
            arc[b][a]=c;
        }
    }
    Prim(arc,1);
    cout<<ans<<endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int NUM=5005;
const int maxn_m=2e5+5;
int S[NUM];//并查集
struct Edge{//定义边
    int u,v,w;
}edge[maxn_m];

bool cmp(Edge a,Edge b){return a.w<b.w;}

//int find(int u){return S[u]==u?u:find(S[u]);}//查询并查集，返回u的根节点

int find(int x)//非递归方式压缩路径
{
    int k, j, r;
    r = x;
    while(r != S[r])     //查找跟节点
        r = S[r];      //找到跟节点，用r记录下
    k = x;
    while(k != r)             //非递归路径压缩操作
    {
        j = S[k];         //用j暂存S[k]的父节点
        S[k] = r;        //S[x]指向跟节点
        k = j;                    //k移到父节点
    }
    return r;         //返回根节点的值
}

int n,m;

int kruskal()
{
    int ans=0;
    for(int i=1;i<=n;i++)S[i]=i;//初始化，开始时每个村庄都是单独的集
    sort(edge+1,edge+1+m,cmp);
    for(int i=1;i<=m;i++)
    {
        int b=find(edge[i].u);//边的前端点u属于哪个集
        int c=find(edge[i].v);//边的后端点v属于哪个集
        if(b==c)continue;//产生圈，丢弃这个边
        S[c]=b;//合并
        ans+=edge[i].w;//计算MST
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    }
    cout<<kruskal()<<endl;
    return 0;
}