纪中第二天（c组）（4）

题目

  Bessie受雇来到John的农场帮他们建立internet网络。农场有 N (2<= N <= 1,000)牛棚，编号为1..N。John之前已经勘测过，发现有 M (1<= M <= 20,000)条可能的连接线路，一条线路是连接某两个牛棚的。每条可能的线路都有一个建设费用 C (1<= C <=100,000)。John当然想花尽量少的钱，甚至克扣Bessie的工钱。

  Bessie发现了这点，很生气，决定给John捣乱。她要选择一些线路组成网，但费用却尽可能大。当然网络要能正常工作，也就是任意两个牛棚之间都是相互可以连通的，并且网络上不能有环，不然John会很容易发现的。

 请计算组建这种网络最多可能的费用。

输入

第一行：两个整数 N M

下面M行：每行3个整数 A，B，C。表示一个可能的线路要连接A、B两个牛棚，费用是C。

输出

只一行，一个整数，即花费最大的费用。如果不可能连接通所有牛棚，输出-1。

样例输入

 5 8
1 2 3
1 3 7
2 3 10       
2 4 4
2 5 8
3 4 6
3 5 2
4 5 17

样例输出

 17 + 8 + 10 + 7 = 42

样例解释

 17 + 8 + 10 + 7 = 42

思路

这是一道明显的最大生成树问题，算法和最小生成树一样，有Prim算法和Kruskal算法，只是把最小边改为最大边而已。我用的是Kruskal算法。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
struct node
{
    int x;
    int y;
    int z;
};
node a[20001];
int father[1001],ans=0,k=0,n,m;
int find(int b)
{
    if(b!=father[b])
        father[b]=find(father[b]);
    return father[b];
}
void unionn(int b,int c)
{
    int d=find(b),e=find(c);
    father[d]=e;
}
bool cmp(node b,node c)
{
    return b.z>c.z;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i].x>>a[i].y>>a[i].z;
    for(int i=1;i<=n;i++)
        father[i]=i;
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        if(find(a[i].x)!=find(a[i].y))
        {
            unionn(a[i].x,a[i].y);
            ans=ans+a[i].z;
            k++;
        }
        if(k==n-1)
        break;
    }
    if(k==n-1)
        cout<<ans<<endl;
    else
        cout<<-1<<endl;
    return 0;
}