【题目描述】

Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。
目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。

【输入】

第一行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表示费用。

【输出】

最小的通信费用。

【输入样例】

5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5

【输出样例】

9

#include<iostream>
#include<algorithm>
using namespace std;
struct point{int p,u,v,w;};
point a[10005];
int father[2005],n,m,k,i,j,tot=0;
int find(int x){
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}
void unite(int x,int y){
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)father[fy]=fx;
}
bool cmp(const point &a,const point &b){
    if(a.w<b.w) return true;
    else return false;  //比较函数
}
int main(){
    cin>>n>>m;
    for(i=1;i<=m;++i){
        cin>>a[i].p>>a[i].u>>a[i].v>>a[i].w;
    }
    for(i=1;i<=n;++i)father[i]=i; 
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=m;++i){ //必选
        if(a[i].p==1){
            tot+=a[i].w;   
            unite(a[i].u,a[i].v);
        }
    }
    for(i=1;i<=m;++i){ //可选
        if(a[i].p==2 && find(a[i].u)!=find(a[i].v)){
            tot+=a[i].w;
            unite(a[i].u,a[i].v);   
        }
    }
    cout<<tot;
    return 0; 
}//网 ok   Kruskal（克鲁斯卡尔）算法