1

我要当第一  •  2个月前


include

include

include

include

define N 2000005

using namespace std; int n,m; long long sum=0,k=0; int fa[N];

struct node {

int u,v,w;

}e[N];

bool cmp(node &a,node &b) {

return a.w<b.w;

} int vis[N]; void init() {

for(int i=1;i<=n;i++)
{
    fa[i]=i;
}

}

int Find(int i) {

if(i==fa[i])
{
    return i;
}
else{
    fa[i]=Find(fa[i]);
    return fa[i];
}

} void unionn(int i,int j) {

int ifa=Find(i);
int jfa=Find(j);
fa[jfa]=ifa;

} void kruskal() {

sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
{
    if(k==n-1)
    {
        break;
    }
    if(Find(e[i].u)!=Find(e[i].v))
    {
        unionn(e[i].u,e[i].v);
        sum+=e[i].w;
        vis[k]=1;
        k++;
    }
}

} int main() {

cin>>n>>m;
for(int i=1;i<=m;i++)
{
    cin>>e[i].u>>e[i].v>>e[i].w;
}
init();
kruskal();
if(k!=n-1)
{
    cout<<"orz";
    return 0;
}
cout<<sum;
return 0;

}


评论:

请先登录,才能进行评论