POJ2377 Bad Cowtractors【Kruskal】【求最大生成树】

Input

* Lines 2..M+1: Each line contains three space-separated integers A, B, and C that describe a connection route between barns A and B of cost C.

Output

Sample Input

Sample Output

Hint

Source

USACO 2004 December Silver

题目大意：Bessie要在John的N个谷仓之间修路，John要求用尽可能少的路使得所有谷仓都能

联通，并且总距离最短，但是他又不想给Bessie钱。Bessie已经意识到John可能不给他钱，所

以他就想把这个工程做的最糟糕并且不让John发现。他决定用尽可能少的路使得所有谷仓都能

联通，但是要使总距离尽可能长。求这个可能的总距离。如果不能使得所有谷仓都联通，则输

出"-1"。

思路：和最小生成树的求法类似，这里使边的权值尽可能大。用Kruskal算法来做，排序的时候，

将边从大到小排序。因为Kruskal算法过程中要先判断两点是否联通，而且边是从大到小排序，所

以如果两点间有重边，则优先选择大的加入生成树中。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1100;
const int MAXM = 40040;
struct EdgeNode
{
    int from;
    int to;
    int w;
}Edges[MAXM];

int father[MAXN];

int find(int x)
{
    if(x != father[x])
        father[x] = find(father[x]);
    return father[x];
}

int cmp(EdgeNode a,EdgeNode b)
{
    return a.w > b.w;
}

void Kruskal(int N,int M)
{
    sort(Edges,Edges+M,cmp);
    int ans = 0,Count = 0;

    for(int i = 0; i < M; ++i)
    {
        int u = find(Edges[i].from);
        int v = find(Edges[i].to);
        if(u != v)
        {
            ans += Edges[i].w;
            father[v] = u;
            Count++;
            if(Count == N-1)
                break;
        }
    }
    if(Count == N-1)
        cout << ans << endl;
    else
        cout << "-1" << endl;
}
int main()
{
    int N,M;
    while(~scanf("%d%d",&N,&M))
    {
        for(int i = 1; i <= N; ++i)
            father[i] = i;
        for(int i = 0; i < M; ++i)
        {
            scanf("%d%d%d",&Edges[i].from, &Edges[i].to, &Edges[i].w);
        }
        Kruskal(N,M);
    }

    return 0;
}

POJ2377 Bad Cowtractors【Kruskal】【求最大生成树】

原文：http://blog.csdn.net/lianai911/article/details/43087591