POJ 2485 Highways：最小生成树 Prim

POJ 2485 Highways：最小生成树 Prim2015-02-25Highways：http://poj.org/problem？id=2485

大意：给你一个用邻接矩阵形式存储的有n个顶点的无向图，让你求它的最小生成树并求出在这个生成树里面最大的边的权值。

思路：用Prim求，判断条件改一下就行。

PS：dis数组初始化的时候用memset一直RE，希望有知道怎么回事的不吝赐教，谢了~

#include <stdio.h>#include <string.h>#define INF 0x3f3f3f3fint Map[510][510];int dis[510];int n, m;int min（int a, int b）{return a > b ？ b : a;}int Prim（）{int Min_ele, Min_node;for（int i = 1; i <= n; i++）{dis[i] = INF;}///这里如果用memset（dis, INF, sizeof（dis））;的话会一直REint r = 1;int Ans = 0;for（int i = 1; i < n; i++）{Min_ele = INF;dis[r] = -1;for（int j = 1; j <= n; j++）{if（j ！= r && 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;if（Min_ele > Ans）Ans = Min_ele;}return Ans;}void Solve（）{scanf（"%d", &m）;while（m--）{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]）;}}printf（"%d
", Prim（））;}}int main（）{Solve（）;return 0;}

From：cnblogs GLsilence