poj2377(最大生成树)

题意：给出点和边，求最大生成树，如果不能生成树，输出-1。

Sample Input

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

Sample Output

42

• Line 1: Two space-separated integers: N（点） and M（边）
• 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.

思路：有N个点，如果共取了N - 1条边，就可以，否则输出-1。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <set>
using namespace std;

const int MAX_N = 1e3 + 5;
const int MAX_M = 2e4 + 5;
int par[MAX_N];
int rank[MAX_N];

struct edge {
    int a, b, cost;
};

edge es[MAX_M];

void init(int n) {
    for (int i = 0; i < n; ++i) {
        rank[i] = 0;
        par[i] = i;
    }
}

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

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return ;
    if (rank[x] < rank[y]) par[x] = y;
    else {
        par[y] = x;
        if (rank[x] == rank[y]) ++rank[x];
    }
}

bool comp(const edge &a, const edge &b) {
    return a.cost > b.cost;
}

int solve(int n, int m) {
    //set<int> s;
    sort(es, es + m, comp);
    int res = 0;
    int ans = 0;//记录有多少条边
    for (int i = 0; i < m; ++i) {
        edge e = es[i];
        if (find(e.a) != find(e.b)) {
            unite(e.a, e.b);
            //s.insert(e.a);
            //s.insert(e.b);
            ++ans;
            res += e.cost;
        }
    }
    //if (s.size() != n) res = -1;//如果这样的话，各个边不一定是联通的，如12，34，s.size() = 4, 符合条件，但不能构成树
    if (ans != n - 1) res = -1;
    return res;
}

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        init(n);
        for (int i = 0; i < m; ++i) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            es[i] = (edge){a - 1, b - 1, c};
        }
        printf("%d\n", solve(n, m));
    }
    return 0;
}