2AC求助
查看原帖
2AC求助
342076
Union_of_Britain楼主2020/11/14 21:21

rt

#include<bits/stdc++.h>
using namespace std;
struct edge
{
  int x,y,w;  
};
edge a[200005];
int ans=0;
int fa[10005];
int cnt=0;
int cmp(edge a,edge b)
{
    return a.w<b.w;
}
int find(int x)
{
    while(x!=fa[x]) x=fa[x]=fa[fa[x]];
    return x;
}
void he(int x,int y)
{
    fa[y]=x;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
    }
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i; 
    }
    for(int i=1;i<=m;i++)
    {
        if(find(a[i].x)==find(a[i].y))
        {
            continue;
        }
        ans+=a[i].w;
        cnt++;   
        he(a[i].x,a[i].y);
        if(cnt==n-1)
        {
            break;
        }

    }
    if(cnt==n-1)
    {
    cout<<ans;
    }
    else
    {
        cout<<"orz";
    }
    return 0;
}
2020/11/14 21:21
加载中...