题目大意：一群牛要修建一些通道，到各个农场距离总和要最小，求这些通道的最大值
水题了，一个Kruskal搞定
#include <iostream>
#include <functional>
#include <algorithm> using namespace std;
typedef int Postion;
typedef struct _edge
{
Postion from;
Postion to;
int cost;
}Edge_Set;
int fcomp(const void *a, const void *b)
{
return (*(Edge_Set *)a).cost - (*(Edge_Set *)b).cost;
} static Edge_Set edge[ * ];
static Postion Set[]; void Kruskal(const int, const int);
Postion Find(Postion);
void Union(Postion, Postion); int main(void)
{
int Node_Sum, Path_Sum;
while (~scanf("%d%d", &Node_Sum, &Path_Sum))
{
for (int i = ; i < Path_Sum; i++)
scanf("%d%d%d", &edge[i].from, &edge[i].to, &edge[i].cost);
qsort(edge, Path_Sum, sizeof(Edge_Set), fcomp);
Kruskal(Node_Sum, Path_Sum);
} return ;
} Postion Find(Postion x)
{
if (Set[x] < )
return x;
return Set[x] = Find(Set[x]);
} void Union(Postion px, Postion py)
{
if (Set[px] < Set[py])
{
Set[px] += Set[py];
Set[py] = px;
}
else
{
Set[py] += Set[px];
Set[px] = py;
}
} void Kruskal(const int Node_Sum, const int Path_Sum)
{
int edge_sum = , max_edge = -;
long long ans = ;
Postion px, py, from, to;
memset(Set, -, sizeof(Set)); for (int i = ; edge_sum < Node_Sum && i < Path_Sum; i++)
{
from = edge[i].from; to = edge[i].to;
px = Find(from); py = Find(to); if (px != py)
{
ans += edge[i].cost;
Union(px, py);
edge_sum++;
max_edge = max(max_edge, edge[i].cost);
}
}
printf("%d\n", max_edge);
}