题目链接
http://poj.org/problem?id=1258
题意
有n个农场，现在要在n个农场之间铺设光纤使得n个农场连接起来，求铺设光纤的最短距离。
思路
最小生成树问题，使用Prime算法或者Kruskal算法解决。
代码
Prime算法：
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 ?7 const int INF = 0x7fffffff; 8 const int N = 100 + 10; 9 int map[N][N];10 int dist[N];11 int n;12 13 void prime()14 {15 ????int min_edge, min_node;16 ????for (int i = 0; i < n; i++)17 ????????dist[i] = INF;18 ????int ans = 0;19 ????int now = 0;20 ????for (int i = 0; i < n - 1; i++)21 ????{22 ????????dist[now] = -1;23 ????????min_edge = INF;24 ????????for (int j = 0; j < n; j++)25 ????????{26 ????????????if (j != now && dist[j] >= 0)27 ????????????{28 ????????????????if (map[now][j]>0)29 ????????????????????dist[j] = min(dist[j], map[now][j]);30 ????????????????if (dist[j] < min_edge)31 ????????????????{32 ????????????????????min_edge = dist[j]; ???//min_edge存储与当前结点相连的最短的边33 ????????????????????min_node = j;34 ????????????????}35 ????????????}36 ????????}37 ????????ans += min_edge;38 ????????now = min_node;39 ????}40 ????printf("%d\n", ans);41 }42 43 int main()44 {45 ????//freopen("poj1258.txt", "r", stdin);46 ????while (scanf("%d", &n) == 1)47 ????{48 ????????memset(map, 0, sizeof(map)); ???//注意初始化49 ????????for (int i = 0; i < n; i++)50 ????????????for (int j = 0; j < n; j++)51 ????????????????cin >> map[i][j];52 ????????prime();53 ????}54 ????return 0;55 }Kruskal算法：
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 #include <vector> 6 using namespace std; 7 ?8 struct Edge 9 {10 ????int a, b, dist;11 12 ????Edge() {}13 ????Edge(int a, int b, int d) :a(a), b(b), dist(d) {}14 };15 16 bool cmp(Edge e1, Edge e2)17 {18 ????return e1.dist < e2.dist;19 }20 21 const int N = 100 + 10;22 vector<Edge> v;23 int p[N];24 int map[N][N];25 int n;26 27 int find_root(int x)28 {29 ????if (p[x] == -1)30 ????????return x;31 ????else return find_root(p[x]);32 }33 34 void kruskal()35 {36 ????memset(p, -1, sizeof(p));37 ????sort(v.begin(), v.end(), cmp); ???//将边按边长从短到长排序38 ????int ans = 0;39 ????for (int i = 0; i < v.size(); i++)40 ????{41 ????????int ra = find_root(v[i].a);42 ????????int rb = find_root(v[i].b);43 ????????if (ra != rb)44 ????????{45 ????????????ans += v[i].dist;46 ????????????p[ra] = rb;47 ????????}48 ????}49 ????printf("%d\n", ans);50 }51 52 int main()53 {54 ????//freopen("poj1258.txt", "r", stdin);55 ????while (scanf("%d", &n) == 1)56 ????{57 ????????v.clear(); ???//注意初始化58 ????????for (int i = 0; i < n; i++)59 ????????????for (int j = 0; j < n; j++)60 ????????????????cin >> map[i][j];61 ????????for (int i = 0; i < n; i++)62 ????????????for (int j = 0; j < n; j++)63 ????????????????if (i < j) v.push_back(Edge(i, j, map[i][j]));64 ????????kruskal();65 ????}66 ????return 0;67 }poj1258 Agri-Net（Prime || Kruskal）
原文地址：http://www.cnblogs.com/sench/p/7967511.html