poj 1251 Jungle Roads(Prim)

Memory: 240K   Time: 0MS

解题思路

题意：

    求走遍所有的村庄最少的花费.村庄从A以字典序开始命名。

 

思路：

   最小生成树，prim算法。

   用lowcost记录每次要走的最小的那条路，走一次更新一次。

最要注意的是输入很变态，用getchar+scanf 会TEL，一定要用cin。

源程序

 

#include

#include <stdio.h>
#include <conio.h>
#define N 28
#define inf 0xffffff

using namespace std;
int g[N][N];
void prim(int n)
{
    int lowcost[N];
    int i, j, min, sum, minid;

    for(i=1; i<=n; i++)
        lowcost[i] = g[1][i];

    lowcost[1] = 0;    //这里我的模版本来用的1，导致后面错了，
    sum = 0;
    for(i=1; i<n; i++)
    {
        min = inf;
        minid = 0;
        for(j=1; j<=n; j++)
        {
            if(lowcost[j] < min && lowcost[j])  //影响到这里
            {
                min = lowcost[j];
                minid = j;
            }
        }
        if(minid)
        {
            sum += min;
            lowcost[minid] = 0;
            for(j=1; j<=n; j++)
            {
                if(g[minid][j] < lowcost[j])
                    lowcost[j] = g[minid][j];
            }
        }
    }
    printf("%d\n", sum);
}

int main()
{
    int i, j;
    int n, m, w;
    char ch, c;
    freopen("in.txt", "r", stdin);
    while(scanf("%d", &n) && n)
    {
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                g[i][j] = inf;
        for(i=1; i<n; i++)
        {
            cin >> ch >> m;
            while(m--)
            {
                cin >> c >> w;
                g[c - 'A'+1][ch - 'A'+1] = g[ch-'A'+1][c-'A'+1] = w;
            }
        }
        prim(n);
    }
    getch();
    return 0;
}