【题目描述】

某个局域网内有n(n≤100)台计算机，由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用f(i,j)表示i,j之间连接的畅通程度(f(i,j)≤1000)，f(i,j)值越小表示i,j之间连接越通畅，f(i,j)为0表示i,j之间无网线连接。现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路，并且被除去网线的Σf(i,j)最大，请求出这个最大值。

【输入】

第一行两个正整数n k
接下来的k行每行三个正整数i j m表示i,j两台计算机之间有网线联通，通畅程度为m。

【输出】

一个正整数，Σf(i,j)的最大值。

【输入样例】

5 5
1 2 8
1 3 1
1 5 3
2 4 5
3 4 2

【输出样例】

8

#include<iostream>
#include<algorithm>
using namespace std;
struct point{int x,y,v;};
point a[10001];
int father[101],n,m,k,i,j,tot=0,sm=0,ct=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.v<b.v)return true;
    else return false;  //升序排序的比较函数
}
int main(){
    cin>>n>>k;
    for(i=1;i<=k;++i){
        cin>>a[i].x>>a[i].y>>a[i].v;
        sm+=a[i].v;
    }
    for(i=1;i<=n;++i)father[i]=i;
    sort(a+1,a+k+1,cmp);
    for(i=1;i<=k;++i){
        if(find(a[i].x)!=find(a[i].y)){
            unite(a[i].x,a[i].y);
            tot+=a[i].v;
            ct++;
        }
        if(ct==n-1)break;
    }
    cout<<sm-tot;
    return 0; 
}//网 ok   Kruskal（克鲁斯卡尔）算法