联络员

• 这道题某种意义上是一个裸的最小生成树。但是并不太一样，因为这道题有必须要选的边。这里可以用缩点的方法来做。在初始化的时候要把每条必须选的边放入并查集中。
• 直接在读入的时候判断类型，如果是必须要选的就直接加入到并查集中。如果不是的话就放到边里面。然后按照kruskal来做就可以。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>

using namespace std;

const int N = 20010;

int p[N];

struct Node
{
    int a;
    int b;
    int w;
} nodes[N];

int n, m;
int res;
int cnt;

bool cmp(Node x, Node y)
{
    return x.w < y.w;
}

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

int main()
{
    cin >> n >> m;
    for (int i = 0; i <= n; i ++ ) p[i] = i;

    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 nodes[cnt ++ ] = {a, b, w};
    }

    sort(nodes, nodes + cnt, cmp);

    for (int i = 0; i < cnt; i ++ )
    {
        int a = nodes[i].a, b = nodes[i].b, w = nodes[i].w;
        int pa = find(a), pb = find(b);

        if (pa != pb)
        {
            res += w;
            p[pa] = pb;
        }
    }

    cout << res << endl;

    return 0;
}