POJ 2485 Highways：最小生成树 Prim

Highways：http://poj.org/problem?id=2485

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

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

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

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

#include <stdio.h>
#include <string.h>
#define INF 0x3f3f3f3f

int 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));的话会一直RE
    int 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\n", Prim());
    }
}

int main()
{
    Solve();

    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， return
， poj
， memset
， 求大神赐教
， prim
， 大神 求解救 谢了
， 生成
最小
poj2485、尼康2485、股市2485、2485原则、尼康2485镜头评测，以便于您获取更多的相关知识。