MST:Agri-Net(POJ 1258)

　　　　　　　　　　　　　 Agri-Net

　　题目大意：农夫有一片农场，现在他要把这些田地用管子连起来，田地之间有一定距离，铺设每一段管子的长度与这些田地与田地距离是一样的，问你最小的铺设方案。

　　这一题很裸，Kruskal算法即可，不过一定要注意，这一题是多组数据输入，边的总数记得初始化！

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