poj2377(Bad Cowtractors)最大生成树

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

42

最大生成树，不能更水的题，kruskal算法排序倒过来就行

#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <limits>
#include <new>
#include <utility>
#include <iterator>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
using namespace std;

struct edge
{
    int u, v, w;
    bool operator < (const edge& b) const
    {
        return w > b.w;
    }
};

edge es[100010];
int V, E;
int f[3100];

void init()
{
    for (int i = 0; i < 3100; ++i)
        f[i] = i;
}

int Find(int x)
{
    return x == f[x] ? x : (f[x] = Find(f[x]));
}

void join(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    f[fx] = fy;
}

int kruskal()
{
    sort(es, es+E);
    init();
    int res = 0;
    for (int i = 0; i < E; ++i)
    {
        edge e = es[i];
        if (Find(e.u) != Find(e.v))
        {
            join(e.u, e.v);
            res += e.w;
        }
    }
    int f = Find(0);
    for (int i = 1; i < V; ++i)
        if (Find(i) != f)
            return -1;
    return res;
}

int main()
{
    scanf("%d%d", &V, &E);
    for (int i = 0; i < E; ++i)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        es[i] = edge{u-1, v-1, w};
    }
    printf("%d\n", kruskal());
    return 0;
}