POJ1251 Jungle Roads 题解

小鱼儿 2021-12-13 21:59 185阅读 0赞

## POJ1251 Jungle Roads 题解 ##

这道是最小生成树简单题，但是我还是认真的做了一个翻译工作:[POJ1251翻译][POJ1251]

Prim:

#include<cstdio>
    #include<cstring>
    #define maxN 30
    #define maxE 
    #define INF 0xffffff
    using namespace std;
    int n;
    int g[30][30];
    int d[30];
    int ans;
    int vis[30];
    void Prim(int v0)
    {
        int i,j,k,minn;  
        memset(vis,0,sizeof(vis));//vis数组清空
        ans=0;//答案清零
        for(i=1;i<=n;i++) d[i]=INF;
        d[v0]=0;
        for(i=1;i<=n;i++)
        {
            minn=INF;
            for(j=1;j<=n;j++)
                if(vis[j]==0 && minn>d[j])minn=d[j],k=j;//查找与生成树距离最小的点
            vis[k]=1;//收入点集
            ans+=d[k];//更新答案
            for(j=1;j<=n;j++) if(vis[j]==0&&d[j]>g[k][j]) d[j]=g[k][j];
            //更新d数组
        }
    }
    int main()
    {
        while(scanf("%d",&n))
        {
            if(n==0) break;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    g[i][j]=INF;//初始化路径花费
                }
                g[i][i]=0;
            }
            for(int i=1;i<n;i++)
            {
                char str[5];//这里尽量使用字符串读入，比较保险
                scanf("%s",str);
                int k;
                scanf("%d",&k);//输入邻接点数量
                for(int j=1;j<=k;j++)
                {
                    char str[5];
                    int val;
                    scanf("%s",str);
                    scanf("%d",&val);
                    int u=str[0]-'A'+1;//记录编号
                    g[i][u]=val;//显然的，这是一个无向图
                    g[u][i]=val;
                }
            }
            Prim(1);
            printf("%d\n",ans);
          /*  for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=n;j++)
                {
                    printf("%2d ",g[i][j]);
                }
                printf("\n");
            }*/
        }
        return 0;
    }

Kruskal

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define maxE 75
    #define maxN 30
    int tot;
    int ans;
    int n;
    struct edge{
        int n1,n2,val;
    }e[maxE];
    int pre[maxN];
    bool cmp(edge a,edge b)
    {
        return a.val<b.val;
    }
    int _find(int x)
    {
        if(pre[x]==x) return x;
        pre[x]=_find(pre[x]);
        return pre[x];
    }
    void Kruskal()
    {
        int k=0;
        ans=0;
        for(int i=1;i<=n;i++)   pre[i]=i;
        for(int i=1;i<=tot;i++)
        {
            int f1=_find(e[i].n1);
            int f2=_find(e[i].n2);
            if(f1!=f2)
            {
                ans+=e[i].val;
                pre[f1]=f2;
                k++;
                if(k==n-1) break;
            }
    
        }
        return;
    }
    int main()
    {
        while(scanf("%d",&n))
        {
            if(n==0) break;
            tot=0;
            for(int i=1;i<n;i++)
            {
                char str[5];
                scanf("%s",str);
                int k;
                scanf("%d",&k);
                for(int j=1;j<=k;j++)
                {
                    char str[5];
                    int val;
                    scanf("%s",str);
                    scanf("%d",&val);
                    int u=str[0]-'A'+1;
                    tot++;
                    e[tot].n1=i;
                    e[tot].n2=u;
                    e[tot].val=val;
                }
            }
            sort(e+1,e+1+tot,cmp);
            Kruskal();
            printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/atlinux/p/11116808.html

[POJ1251]: https://hadermimosaacrux.com/2019/01/20/POJ1251-Jungle-Roads-%E7%BF%BB%E8%AF%91/