kruskal变形

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010 , M = 10010;

int n , m;
int p[N];
struct Edge
{
    int a , b , w;
    bool operator< (const Edge &t) const 
    {
        return w < t.w;
    }
}e[M];

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

int main()
{
    cin >> n >> m;

    for(int i = 1 ; i <= n ; i ++ ) p[i] = i;

    int res = 0 , k = 0;
    for(int i = 0 ; i < m ; i ++ )
    {
        int t , a , b , w;
        cin >> t >> a >> b >> w;
        if(t == 1)
        {
            p[find(a)] = find(b);//必选边加到连通块
            res += w;
        }
        else e[k ++ ] = {a , b , w};//不是必选边 
    }
    sort(e , e + k);

    for(int i = 0 ; i < k ; i ++ )
    {
        int a = e[i].a , b = e[i].b , w = e[i].w;
        a = find(a) , b = find(b);
        if(a != b)
        {
            p[a] = b;
            res += w;
        }
    }

    cout << res << endl;

    return 0;
}