洛谷——P 3366【テンプレート】最小生成木

タイトルの説明

  ，       ，       ，       ，   orz

入力形式:

         N、M，      N    M    。（N<=5000，M<=200000）
   M         Xi、Yi、Zi，        Zi        Xi、Yi

出力フォーマット:

       ，              ；          orz

問題:

       ，       。

コード:

#include
#include 
#include 
using namespace std;

struct arr{
    int x,y,z;
}a[2000001];
int  o,p,n,m,k,tot,ans,f[2000001];

int find(int x){
  if (f[x]==x) return f[x];
  f[x]=find(f[x]);
  return f[x];
}

bool cmp(arr a,arr b) {  
    return a.zint main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
    sort(a+1,a+1+m,cmp);
    for (int i=1;i<=n;i++) f[i]=i;
    tot=1; k=ans=0;
    while (totif (o!=p){
            ans+=a[k].z;
            f[o]=p;
            tot++;
        }
    }
    printf("%d ",ans);
}