莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 必须选的道路可提前加上，并将它们放在同一个连通块中
2. 有选择性的道路就按照 Kruskal 算法进行选择

可参考： Kruskal算法求最小生成树

#include<bits/stdc++.h>

using namespace std;

const int N = 2010, M = 10010;

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

//并查集基本操作
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;
    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[cnt++]={a,b,w};
    }

    //排序
    sort(e,e+cnt);

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

    cout<<res<<endl;

    return 0;
}