Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- struct DSU{
- vector<int> p;
- DSU(int n){
- p = vector<int>(n, -1);
- }
- int get(int x){
- if(p[x]<0) return x;
- return p[x] = get(p[x]);
- }
- bool same_set(int x, int y){
- return get(x) == get(y);
- }
- bool unite(int x, int y){
- x = get(x);
- y = get(y);
- if(x == y) return false;
- if(p[x]>p[y]) swap(x, y);
- p[x]+=p[y];
- p[y] = x;
- return true;
- }
- };
- struct Con{
- int a, b;
- int cost;
- bool operator<(const Con &v) const{
- return cost<v.cost;
- }
- };
- int n, m;
- vector<Con> con;
- int cost;
- int main(){
- //freopen("baseprice.in", "r", stdin);
- cin >> n >> m;
- con.resize(m);
- for(int i=0; i<m; i++){
- cin >> con[i].a >> con[i].b >> con[i].cost;
- }
- sort(con.begin(), con.end());
- DSU dsu(n+1);
- for(int i=0; i<m; i++){
- if(!dsu.same_set(con[i].a, con[i].b)){
- dsu.unite(con[i].a, con[i].b);
- cost+=con[i].cost;
- }
- }
- cout << cost << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
