[BZOJ1232][Usaco2008Nov]安慰奶牛cheer 最小生成树



注意到除根节点外,每个节点在最后的生成树中被访问次数即为其度数,因此将点权直接转移到边权上跑kruskal即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 10233
#define M 202333
using namespace std;
int n,m,c[N],head[N],ans=0x3bbbbbbb;
struct Node
{
    int x,y,z;
}e[M];
inline bool operator<(const Node &x,const Node &y)
{
    return x.z<y.z;
}
int fa[N];
int find(int x)
{
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        fa[i]=i;
        scanf("%d",&c[i]);
        ans=min(ans,c[i]);
    }
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
        e[i].z<<=1;
        e[i].z+=c[e[i].x]+c[e[i].y];
    }
    sort(e+1,e+m+1);
    for(int x,y,i=1;i<=m;++i)
    {
        x=find(e[i].x),y=find(e[i].y);
        if(x==y)continue;
        fa[x]=y,ans+=e[i].z;
    }
    cout<<ans;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注