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

Agri-Net：http://poj.org/problem?id=1258

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

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

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

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

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

int dis[110];
int Map[110][110];
int n;
int Ans;

int min(int a, int b)
{
    return a > b ? b : a;
}

void  Prim()
{
    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\n", Ans);
    }
}

int main()
{
    Solve();

    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索map
， int
， prim
， 稀疏编码 求程序
最小
poj1258、1258卡盟、愚园路1258号、g1258、qq5.3.0.1258，以便于您获取更多的相关知识。