hdu 1233 还是畅通工程

深碍√TFBOYSˉ_ 2024-04-17 05:28 67阅读 0赞

### hdu 1233 还是畅通工程 ###

*  题意
 *  题解
 *  源代码

[传送门][Link 1]

# 题意 #

给定n个村子，和每个村子之间的距离，现在要求连接这n个村子的最小距离

# 题解 #

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

# 源代码 #

#include<cstdio>
    const int maxn = 1e2+2;
    
    int g[maxn][maxn];
    int n;
    int dist[maxn];//利用prime算法存储剩余点到最小生成树的最小距离
    int visit[maxn];//记录点是否加入最小生成树点集之中。
    
    int prime(){ 
       //首先将1加入最小生成树点集中，并初始化dist，与visit
       for(int i=1;i<=n;++i)dist[i]=g[1][i],visit[i]=false;
       visit[1]=true;
       while(true){ 
           int index=-1, mmin =1<<30;
           //找出在剩余点集中到最小生成树的距离最小的编号，并加入到最小生成树点集中
           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];
           // 更新dist，判断新加入的点与剩余的点之间的最短距离
       }
       int ans =0;
       for(int i=1;i<=n;++i)ans+=dist[i];
       return ans;
    }
    
    int main(){ 
        int m,a,b,w;
        while(~scanf("%d",&n)&&n){ 
            m=n*(n-1)/2;//边数
            for(int i=0;i<m;++i){ 
                scanf("%d%d%d",&a,&b,&w);
                g[a][b]=g[b][a]=w;
            }
            printf("%d\n",prime());
        }
    }

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