挖沟

裸的最小生成树，带并查集的克鲁斯卡尔算法，为什么这么水的题目我要写题解，大概是为了达目标的打卡吧

# include <cstdio>
# include <cstring>
# include <cctype>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;

const int debug = 1;
const int size  = 5000 + 10; 
const int INF = INT_MAX>>1;
typedef long long ll;

typedef pair<int, int> pir;
// first to, second v

struct DisjointSet{
    int *T,size,sum;
    int FindRoot(int i){
        return T[i] < 0 ? i : T[i] = FindRoot(T[i]);
    }
    DisjointSet(){}
    DisjointSet(int _size):size(_size){
        T = new int[size];
        Init();
    }
    void Init(){sum = size;memset(T,-1,sizeof(int)*size);}
    bool Unioned(int i,int j){return FindRoot(i)==FindRoot(j);}
    int Union(int i,int j){
        if ( (i = FindRoot(i) ) != ( j = FindRoot(j) ) ){
            T[i] = T[i] + T[j];
            T[j] = i;
            sum--;
        }
        return -T[i];
    }
    int GetSum(int i){return -T[FindRoot(i)];}
};

typedef pair<int, int> pir;

vector<pir> edge;
vector<int> w;

int main(){
    // std::ios::sync_with_stdio(false);cin.tie(0);
    int n, m; cin >> n >> m;
    DisjointSet Dst(n);
    priority_queue<pir, vector<pir>, greater<pir> > pri_que;
    while (m--){
        int a, b, c; cin >> a >> b >> c;
        edge.push_back(pir(a, b));
        w.push_back(c);

        pri_que.push(pir(c, w.size()-1));
    }
    int ans = 0;
    while (!pri_que.empty()){
        pir T = pri_que.top(); pri_que.pop();
        int i = edge[T.second].first;
        int j = edge[T.second].second;
        if (!Dst.Unioned(i, j)){
            Dst.Union(i, j);
            ans += T.first;
        }
    }
    cout << ans << endl;
    return 0;
}