[知识点]-[最小生成树]
最小生成树
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)using namespace std;const int N = 1e6+5;int n,m;
int acc[N];
pair<int,pair<int,int>> va[N];int find(int x)
{if(x!=acc[x]) acc[x] = find(acc[x]);return acc[x];
}void krukal()
{int sum = 0,cnt = 0;for(int i=1;i<=n;i++) acc[i] = i;for(int i=1;i<=m;i++){int a = va[i].se.fi,b = va[i].se.se,c = va[i].fi;int t1 = find(a),t2 = find(b);if(t1!=t2){acc[t1] = t2;sum += c;cnt++;}}if(cnt==n-1) cout<<sum;else cout<<"orz";
}int main()
{IOS;cin>>n>>m;for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;va[i] = {c,{a,b}};}sort(va+1,va+1+m);krukal();return 0;
}