hdu 1863 畅通工程

骑猪看日落 2024-04-17 05:35 28阅读 0赞

### hdu 1863 畅通工程 ###

*  题意
 *  题解
 *  源代码

[传送门][Link 1]

# 题意 #

给定n个村子，和m个可能要修的道路，现在要求连接这n个村子的最小成本,如果
    无法构成一颗最小生成树，则输出？

# 题解 #

这题典型的最小生成树模板题，krusal算法和prim算法都可以达到要求
    并且这题的数据量不大，并且是完全图，利用邻接矩阵做就好

# 源代码 #

#include<cstdio>
    const int maxn = 1e2+2;
    const int INF = 1<<30;
    int g[maxn][maxn];
    int n;
    int dist[maxn];//利用prime算法存储剩余点到最小生成树的最小距离
    int visit[maxn];//记录点是否加入最小生成树点集之中。
    
    
    void init(){ 
        for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)g[i][j]=INF;
        //初始化图，不存在记为无穷大INF
    }
    
    int prime(){ 
       //首先将1加入最小生成树点集中，并初始化dist，与visit
       for(int i=1;i<=n;++i)dist[i]=g[1][i],visit[i]=false;
       visit[1]=true;
       dist[1]=0;
       while(true){ 
           int index=-1, mmin =INF;
           //找出在剩余点集中到最小生成树的距离最小的编号，并加入到最小生成树点集中
           for(int i=1;i<=n;++i)if(!visit[i]&&mmin>dist[i])mmin = dist[i],index=i;
           if(index==-1)break;
           //未找到，代表无法有点加入到最小生成树点集中
           visit[index]=true;
           for(int i=1;i<=n;++i)if(!visit[i]&&dist[i]>g[index][i])dist[i]=g[index][i];
           //更新，新加入的点与剩下的点的最小距离关系
       }
       int ans =0;
       for(int i=1;i<=n;++i){ 
           if(dist[i]==INF)return -1;//存在点仍为最小生成树点集中，即无法构成最小生成树
           ans+=dist[i];
       }
       return ans;
    }
    
    int main(){ 
        int m,a,b,w;
        while(~scanf("%d%d",&m,&n)&&m){ 
            init();//初始化图
            for(int i=0;i<m;++i){ 
                scanf("%d%d%d",&a,&b,&w);
                g[a][b]=g[b][a]=w;
            }
            int ans = prime();
            if(ans==-1)printf("?\n");
            else printf("%d\n",ans);
        }
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1863