POJ 1251：Jungle Roads（最小生成树）

傷城~ 2023-06-06 10:53 25阅读 0赞

# POJ 1251：Jungle Roads（最小生成树） #

[题目链接][Link 1]

这道题一起那好像看到过一次，但是由于题目太长就没做，其实一看图就知道是个最小生成树题，昨天心血来潮做了下，结果很无语，一直RE。。。。。

开始用的gechar来输入空格：

getchar();
    scanf("%c",&ch);

但是不知道POJ为啥就是不能过，后面改成这样

scanf(" %c",&ch);

结果就A了，很无语…

当然题目很简单，直接就是个裸的最小生成树，我用的Prim算法  
Prim算法具体实现请看这篇博客：

[最小生成树概念及其构建（Prim算法、Kruskal算法）][Prim_Kruskal]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define INF 999999
    using namespace std;
    int n;
    int mp[110][110];
    int vis[110];
    int cost[110];
    int tree[110];
    void init(){
        
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=n;j++){
        
                if(j==i)
                    mp[i][j]=0;
                else
                    mp[i][j]=INF;
            }
        }
    }
    void Prim(){
        
        memset(vis,0,sizeof(vis));
        memset(cost,0,sizeof(cost));
        memset(tree,0,sizeof(tree));
        for(int i=2;i<=n;i++){
        
            cost[i]=mp[1][i];
            tree[i]=1;
        }
        tree[1]=-1;
        vis[1]=1;
        cost[1]=0;
        for(int i=1;i<=n;i++){
        
            int Min=INF+1;
            int pos;
            for(int j=1;j<=n;j++){
        
                if(vis[j]==0&&cost[j]<Min){
        
                    Min=cost[j];
                    pos=j;
                }
            }
            vis[pos]=1;
            for(int j=1;j<=n;j++){
        
                if(vis[j]==0&&mp[pos][j]<cost[j]){
        
                    cost[j]=mp[pos][j];
                    tree[j]=pos;
                }
            }
        }
    }
    int main(){
        
        while(~scanf("%d",&n)){
        
            if(n==0)
                break;
            init();
            char ch;
            int x,y;
            int m;
            int dis;
            for(int k=0;k<n-1;k++){
        
                scanf(" %c",&ch);
                x=ch-'A'+1;
                scanf("%d",&m);
                for(int i=0;i<m;i++){
        
                    getchar();
                    scanf(" %c %d",&ch,&dis);
                    y=ch-'A'+1;
                    if(mp[x][y]>dis){
        
                        mp[x][y]=mp[y][x]=dis;
                    }
                }
            }
            Prim();
            int sum=0;
            for(int i=1;i<=n;i++){
        
                sum+=cost[i];
            }
            printf("%d\n",sum);
        }
        return 0;
    }

[Link 1]: http://poj.org/problem?id=1251
[Prim_Kruskal]: https://blog.csdn.net/boliu147258/article/details/96324856