題目URL:https://pc2.tfcis.org/dev/index.php/problem/view/43/

MST的裸題，簡單來說只要把operator的比較換一下，就變最大生成樹了，然後順便善用dsu並且小複習。(清大營隊進修ing)

#pragma GCC osptimize("O2")
#include<bits/stdc++.h>
#define int long long int
#define IOS ios_base::sync_with_stdio(false)
#define TI cin.tie(NULL)
using namespace std;
const int MI=100005;
int num,a,b,w;
struct edge{
    int from,to,weight;
};
bool operator < (edge &a,edge &b)
{
    return a.weight > b.weight;
}
vector<edge> v;
int vnum,vedge;
struct disjointset{
    int f[MI],rank[MI];
    void init(int N)
    {
        for(int i=0;i<=N;i++)
        {
            f[i]=i;
            rank[i]=0;
        } 
    }
    int find(int val)
    {
        if(f[val]==val) return val;
        return f[val]=find(f[val]);
    }
    bool same(int a,int b)
    {
        return find(a)==find(b);
    }
    void Union(int l,int r)
    {
        if(!same(l,r))
        {
            if(rank[l]<rank[r]) swap(l,r);
            f[f[r]]=f[l];
            rank[l]++;
        }
    }
};
int kruskal(void)
{
    sort(v.begin(),v.end());
    struct disjointset dsu;
    dsu.init(vnum);
    int total=0;
    for(int i=0,cou=0; i<vedge && cou<vnum ;i++)
    {
        int x=v[i].from,y=v[i].to;
        //cout << "x=" <<x << "y=" << y <<endl;
        if(!dsu.same(x,y))
        {  
            total+=v[i].weight;
            cou++;
            dsu.Union(x,y);
        }
    }
    //cout <<"total="<<total <<endl;
    return total;
}
main()
{
    IOS;TI;
    cin >> num;
    while(num--)
    {
        cin >> vnum >> vedge;
        struct edge cpy;
        for(int i=0;i<vedge;i++)
        {
            cin >> a >> b >> w;
            cpy.from=a;
            cpy.to=b;
            cpy.weight=w;
            v.push_back(cpy);
        }
    int ans=kruskal();
    cout << ans << endl;
    while(!v.empty())
        v.pop_back();
    }
    return 0;
}