计蒜客灌溉（最小生成树之prim算法）

落日映苍穹つ 2024-02-17 22:14 51阅读 0赞

到了旱季农业生产的灌溉就成了一个大问题。为了保证灌溉的顺利，某县政府决定投资为各个村之间建立灌溉管道。

输入第1行包括一个整数N，表示某县的村庄的数量。（3≤N≤100），第2行-结尾为一个N×N的矩阵,表示每个村庄之间的距离。虽然在理论上，他们是N行，每行由N个用空格分隔的数组成，实际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个村到它本身（任何两个村之间的距离都不大于100000）。

输出只有一个，为修建灌溉管道将所有村庄相连在一个灌溉系统里所需的最小管道长度。

##### 样例输入 #####

4
    0 4 9 21
    4 0 8 17
    9 8 0 16
    21 17 16 0

##### 样例输出 #####

28

生成树之prim算法；

AC代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define INF 100000000
    const int maxn=100+5;
    int g[maxn][maxn];
    int vis[maxn];
    int d[maxn];
    int N;
    
    int prim(){
        int ans=0;
        memset(vis,0,sizeof(vis));
        for(int i=0;i<N;i++)
        d[i]=g[0][i];
        vis[0]=1;
    	
    	for(int i=0;i<N-1;i++){
    		int Min=INF;
    		int t; 
    		for(int j=0;j<N;j++){
    		    if(!vis[j]&&Min>d[j]){
    		    	Min=d[j];
    		    	t=j;
    			}
    		}
    		vis[t]=1;
    		ans+=Min;
    		
    		for(int k=0;k<N;k++){
    			d[k]=min(d[k],g[t][k]);
    		}
    	}
        return ans;
    }
    
    int main(){
    	while(scanf("%d",&N)==1){
    		for(int i=0;i<N;i++){
    			for(int j=0;j<N;j++)
    			scanf("%d",&g[i][j]);
    		}
    		
    		int ans = prim();
    		printf("%d\n",ans);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，51人围观）

还没有评论，来说两句吧...

相关阅读

相关计蒜客灌溉（最小生成树之prim算法）

到了旱季农业生产的灌溉就成了一个大问题。为了保证灌溉的顺利，某县政府决定投资为各个村之间建立灌溉管道。输入第1行包括一个整数N，表示某县的村庄的数量。（3≤N≤100），第

落日映苍穹つ/ 2024年02月17日 22:14/ 0 赞/ 52 阅读

相关最小生成树--prim算法

include<bits/stdc++.h> using namespace std; const int N=5010,INF=0x3f3f3f3f;

痛定思痛。/ 2023年07月15日 04:59/ 0 赞/ 246 阅读

相关最小生成树之 Prim算法 & Kruskal算法

1 描述问题：修建一个连接各个小区与煤气供应站点之间的管道，使得造价成本最低，即构造一颗最小生成树。但是如何求解？对应模型：树结构，生成树，最小生成树 2 pr

梦里梦外;/ 2023年02月28日 01:36/ 0 赞/ 122 阅读

相关最小生成树之prim算法

边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。最小生成树（MST）：权值最小的生成树。生成树和最小生成

港控/mmm°/ 2022年09月25日 09:24/ 0 赞/ 190 阅读

相关 prim算法模板—最小生成树

设G = (V,E)是无向连通带权图，即一个网络。E中的每一条边（v,w）的权为c\[v\]\[w\]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G

冷不防/ 2022年08月11日 04:29/ 0 赞/ 184 阅读

相关最小生成树prim算法

无向图 ![这里写图片描述][SouthEast] 最小生成树 ![这里写图片描述][SouthEast 1] /最小生成树prim算法/ inc

川长思鸟来/ 2022年06月14日 00:41/ 0 赞/ 238 阅读

相关最小生成树-Prim算法

最小生成树的目的是使一个图的节点到其他各个节点的距离最短。产生的树成为最小生成树。最小生成树算法分为普利姆（Prim）算法与克鲁斯卡尔（Kruskal）算法来解决。

红太狼/ 2022年06月10日 12:49/ 0 赞/ 238 阅读

相关最小生成树———灌溉

到了旱季农业生产的灌溉就成了一个大问题。为了保证灌溉的顺利，某县政府决定投资为各个村之间建立灌溉管道。输入第1行包括一个整数N，表示某县的村庄的数量。（3≤N≤10

雨点打透心脏的1/2处/ 2022年06月07日 12:17/ 0 赞/ 144 阅读

相关最小生成树（Prim）算法

算法思想：假设`G=<V,E>`是连通图，TE是G上最小生成树中边的集合。算法从U=\{u0\}(u0∈V)，TE=\{ \}开始，任取一个顶点u0作为开

朴灿烈づ我的快乐病毒、/ 2022年06月05日 01:10/ 0 赞/ 263 阅读

相关 prim算法--最小生成树

首先我们在这里先介绍一下prim算法，我记得大学数据结构先讲完最小生成树，再讲最短路径，也是考研必考问题。 prim算法在加权连通图里面寻找全局最小的生成树。是一个贪心算法。

悠悠/ 2021年11月17日 02:28/ 0 赞/ 463 阅读