POJ2377Bad Cowtractors(最大生成树)

POJ2377Bad Cowtractors(最大生成树)

POJ2377Bad Cowtractors

题目大意:给一个带权无向图，求最大生成树。

解题思路： 
因为最小生成树按照kruskal的贪心算法是可以证明正确的，那么反向我们取最大的权值的边，然后不断的加入形成的生成树就是最大生成树。

代码：

#include <cstdio>
#include <algorithm>using namespace std;const int maxn = 1005;
const int maxm = 20005;int N, M;
int p[maxn];
struct edge {int u, v, cost;
}e[maxm];void init () {for (int i = 1; i <= N; i++)p[i] = i;
}int getParent (int x) {return x == p[x] ? x : p[x] = getParent(p[x]);
}int cmp (const edge& a, const edge& b) {return a.cost > b.cost;
}int main () {while (scanf ("%d%d", &N, &M) != EOF ){for (int i = 0; i < M; i++)scanf ("%d%d%d", &e[i].u, &e[i].v, &e[i].cost);sort(e, e + M, cmp);init();int count = 0;int ans = 0;for (int i = 0; i < M; i++) {int p1 = getParent (e[i].u);int p2 = getParent (e[i].v);if (p1 != p2) {ans += e[i].cost;p[p1] = p2;count++;}if (count == N - 1)break;}if (count == N - 1)printf ("%d\n", ans);elseprintf ("-1\n");}return 0;
}