POJ2377 Bad Cowtractors(最大生成树)

题意：

连接农场，要求输出最大权值和并且不能连成环，如果不能全部连接，输出-1

要点;

就是最小生成树变成最大罢了，Kruskal算法，排序改成从大到小，一次AC。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define maxn 100050
using namespace std;
int p[maxn];
int m, n;
struct edge
{int u, v, len;
}e[maxn];bool cmp(edge a, edge b)
{return a.len > b.len;
}
void init()
{for (int i = 1; i <= m; i++)p[i] = i;
}
int find(int x)
{if (p[x] == x) return x;return p[x] = find(p[x]);
}
bool merge(int x, int y)
{x = find(x);y = find(y);if (x != y){p[x] = y;return true;}return false;
}
int kruskal()
{init();sort(e, e + n, cmp);int sum = 0, edges = 0;for (int i = 0; i < n; i++){if (merge(e[i].u, e[i].v)){sum += e[i].len;edges++;}if (edges + 1 == m)return sum;}return -1;
}int main()
{while (~scanf("%d%d", &m, &n)){for (int i = 0; i < n; i++)scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].len);printf("%d\n", kruskal());}return 0;
}