MST:Bad Cowtractors(POJ 2377)

　　　　　　　　　　　　　　　　　坏的牛圈建筑

　　题目大意：就是现在农夫又要牛修建牛栏了，但是农夫想不给钱，于是牛就想设计一个最大的花费的牛圈给他，牛圈的修理费用主要是用在连接牛圈上

　　这一题很简单了，就是找最大生成树，把Kruskal算法改一下符号就好了，把边从大到小排列，然后最后再判断是否联通（只要找到他们的根节点是否相同就可以了！）

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <functional>
  4 #define MAX_N 1005
  5 #define MAX 20005
  6 
  7 using namespace std;
  8 
  9 typedef int Position;
 10 typedef struct _edge
 11 {
 12     Position from;
 13     Position to;
 14     int cost;
 15 }Edge_Set;
 16 int fcomp(const void *a, const void *b)
 17 {
 18     return (*(Edge_Set *)b).cost - (*(Edge_Set *)a).cost;
 19 }
 20 
 21 static Edge_Set edge[MAX];
 22 static Position Set[MAX_N];
 23 
 24 Position Find(Position);
 25 void Union(Position, Position);
 26 void Kruskal(const int, const int);
 27 bool Is_Connected(const int);
 28 
 29 int main(void)
 30 {
 31     int Node_Sum, Path_Sum, cost;
 32     Position tmp_from, tmp_to;
 33 
 34     while (~scanf("%d%d", &Node_Sum, &Path_Sum))
 35     {
 36         for (int i = 0; i < Path_Sum; i++)//读入边
 37         {
 38             scanf("%d%d%d", &tmp_from, &tmp_to, &cost);
 39             edge[i].from = tmp_from; edge[i].to = tmp_to; edge[i].cost = cost;
 40         }
 41         qsort(edge, Path_Sum, sizeof(Edge_Set), fcomp);
 42         Kruskal(Node_Sum, Path_Sum);
 43     }
 44     return 0;
 45 }
 46 
 47 Position Find(Position x)
 48 {
 49     if (Set[x] < 0)
 50         return x;
 51     else return Set[x] = Find(Set[x]);
 52 }
 53 
 54 void Union(Position px, Position py)
 55 {
 56     if (Set[px] < Set[py])
 57     {
 58         Set[px] += Set[py];
 59         Set[py] = px;
 60     }
 61     else
 62     {
 63         Set[py] += Set[px];
 64         Set[px] = py;
 65     }
 66 }
 67 
 68 bool Is_Connected(const int Node_Sum)
 69 {
 70     Position p_u, p_tmp;
 71     p_u = Find(1);
 72     for (int i = 2; i <= Node_Sum; i++)
 73     {
 74         p_tmp = Find(i);
 75         if (p_u != p_tmp)
 76             return false;
 77     }
 78     return true;
 79 }
 80 
 81 void Kruskal(const int Node_Sum, const int Path_Sum)
 82 {
 83     Position px, py, from, to;
 84     long long ans = 0;
 85 
 86     fill(Set, Set + Node_Sum + 1, -1);
 87     for (int i = 0; i < Path_Sum; i++)
 88     {
 89         from = edge[i].from; to = edge[i].to;
 90         px = Find(from); py = Find(to);
 91 
 92         if (px != py)
 93         {
 94             ans += edge[i].cost;
 95             Union(px, py);
 96         }
 97     }
 98     if (Is_Connected(Node_Sum))
 99         printf("%lld
", ans);
100     else
101         printf("-1
");
102 }