联络员

Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。本题中所涉及的通信渠道都是双向的。

Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。

目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。

数据保证给出的通信渠道可以让所有的管理员联通。

注意： 对于某两个管理员 u,v，他们之间可能存在多条通信渠道，你的程序应该累加所有 u,v 之间的必选通行渠道。

输入格式

第一行两个整数 n，m表示Tyvj一共有 n 个管理员，有 m 个通信渠道;

第二行到 m+1 行，每行四个非负整数，p,u,v,w 当 p=1 时，表示这个通信渠道为必选通信渠道；当 p=2 时，表示这个通信渠道为选择性通信渠道；u,v,w 表示本条信息描述的是 u，v管理员之间的通信渠道，u 可以收到 v 的信息，v 也可以收到 u 的信息，w 表示费用。

输出格式

一个整数，表示最小的通信费用。

数据范围

1≤n≤2000
1≤m≤10000

输入样例：

输出样例：

思路

将必须建边的点放在一个集合，然后接着做一次克鲁斯卡尔算法。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2010,M=20010;
struct eg{
    int u,v,w;
}e[M];
int fa[N];
int Find(int x){
    return fa[x]==x? x: fa[x]=Find(fa[x]);
}
bool cmp(eg a,eg b){
    return a.w<b.w;
}
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;++i) fa[i]=i;
    int res=0,tot=0;
    for(int i=1;i<=m;++i){
        int p,u,v,w;
        cin>>p>>u>>v>>w;
        if(p==1) {
            res+=w;
            int fu=Find(u),fv=Find(v);
            if(fu!=fv) fa[fu]=fv;
        }
        else e[++tot]=(eg){u,v,w};
    }
    sort(e+1,e+tot+1,cmp);
    for(int i=1;i<=tot;++i){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        int fu=Find(u),fv=Find(v);
        if(fu!=fv) fa[fu]=fv,res+=w;
    }
    cout<<res<<endl;
    return 0;
}