prim 模板

#include<cstdio>

#include<vector>

#include<cstring>

#include<set>

#define maxn 5050

#define fi first

#define se second

using namespace std;

typedef pair<int,int> PII;

vector <PII> s[maxn];

int map[][];

int low_cost[maxn],zou[maxn],n,m,x,y,val,zhong,mi,ans;

int up(int x,int y,int val)

{

    for(int i=;i<s[x].size();i++)

    {

        if(s[x][i].fi==y )

        {

            if( s[x][i].se>val)

            {

                s[x][i].se=val;

            }

            return ;

        }

    }

    return ;

}

main(){

//    freopen("data.in","r",stdin);

    scanf("%d%d",&n,&m);

    memset(low_cost,/,sizeof(low_cost));

//    memset(map,127/3,sizeof(map));

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%d",&x,&y,&val);

        if(x==y) continue;

//        map[x][y]=min(map[x][y],val);

//        map[y][x]=min(map[y][x],val);

        if(up(x,y,val))

            up(y,x,val);

        else

        {

            s[x].push_back(PII(y,val));

            s[y].push_back(PII(x,val));

        }

    }

    for(int i=;i<s[].size();i++)

    {

        low_cost[s[][i].fi]=s[][i].se;

    }

/*    for(int i=2;i<=n;i++)

    {

        low_cost[i]=min(low_cost[i],map[1][i]);

    }*/

    zou[]=;

    zhong=;

    for(int qwer=;qwer<n;qwer++)

    {

        int f=;

        mi=;

        for(int i=;i<=n;i++)

        {

            if(low_cost[i]<mi && zou[i]==)

            {

                mi=low_cost[i];

                zhong=i;

                f=;

            }

        }

        if(f==)

        {

            printf("orz");

            return ;

        }

        ans+=mi;

        zou[zhong]=;

        for(int i=;i<s[zhong].size();i++)

        {

            if(zou[s[zhong][i].fi]==) continue;

            low_cost[s[zhong][i].fi]=min(low_cost[s[zhong][i].fi],s[zhong][i].se);

        }

/*        for(int i=1;i<=n;i++)

        {

            if(map[zhong][i]<low_cost[i])

                low_cost[i]=map[zhong][i];

        }*/

    }

    printf("%d",ans);

}