联络员

这个题必须要加的就加进去，不必须加的就做kruskal最小生成树就行了

代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;
int n, m, p[N], res;

struct Edge 
{
    int u, v, w;
    bool operator <(const Edge& W) const {
        return w < W.w;
    }
} edge[N];

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

int Krus() 
{
    sort(edge + 1, edge + 1 + m);

    for (int i = 1; i <= m; i ++ ) 
    {
        int fu = find(edge[i].u), fv = find(edge[i].v);
        if (fu == fv) continue ;

        p[fu] = fv, res += edge[i].w;
    }

    return res;
}

int main() 
{
    scanf("%d%d", &n, &m);

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

    for (int i = 1; i <= m; i ++ ) 
    {
        int P, u, v, w;
        scanf("%d%d%d%d", &P, &u, &v, &w);
        if (P == 1) res += w, p[find(u)] = find(v);
        edge[i] = {u, v, w};
    }

    printf("%d\n", Krus());

    return 0;
}