POJ 1258 Agri-Net：最小生成树 Prim 模版题

POJ 1258 Agri-Net：最小生成树 Prim 模版题2015-02-25Agri-Net：http://poj.org/problem？id=1258

大意：新镇长竞选宣言就是将网络带到每一个农场，给出农场个数，两两之间建光缆的耗费，求所有都联通的最小耗费。

思路：最小生成树，因为边比较稠密，用Prim做。

PS；对于比较稠密的图，用Prim，对于比较稀疏的图，用 Kruskal。Kruskal是找边的过程，稀疏的话会比较快。

#include <stdio.h>#include <string.h>#define INF 0x3f3f3f3fint dis[110];int Map[110][110];int n;int Ans;int min（int a, int b）{return a > b ？ b : a;}voidPrim（）{int Min_ele, Min_node;memset（dis, INF, sizeof（dis））;Ans = 0;int r = 1;for（int i = 1; i < n; i++）{dis[r] = -1;Min_ele = INF;for（int j = 1; j <= n; j++）{if（dis[j] >= 0）{dis[j] = min（dis[j], Map[r][j]）;if（dis[j] < Min_ele）{Min_ele = dis[j];Min_node = j;}}}r = Min_node;Ans += Min_ele;}}void Solve（）{while（~scanf（"%d", &n））{memset（Map, 0, sizeof（Map））;for（int i = 1; i <= n; i++）{for（int j = 1; j <= n; j++）{scanf（"%d", &Map[i][j]）;}}Prim（）;printf（"%d
", Ans）;}}int main（）{Solve（）;return 0;}

From：cnblogs GLsilence