首页 > 代码库 > hihocoder hiho一下 第二十六周 最小生成树一·(Prim算法)
hihocoder hiho一下 第二十六周 最小生成树一·(Prim算法)
题目1 : 最小生成树一·Prim算法
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
最近，小Hi很喜欢玩的一款游戏模拟城市开放出了新Mod，在这个Mod中，玩家可以拥有不止一个城市了！
但是，问题也接踵而来——小Hi现在手上拥有N座城市，且已知这N座城市中任意两座城市之间建造道路所需要的费用，小Hi希望知道，最少花费多少就 可以使得任意两座城市都可以通过所建造的道路互相到达（假设有A、B、C三座城市，只需要在AB之间和BC之间建造道路，那么AC之间也是可以通过这两条 道路连通的）。
提示：不知道为什么Prim算法和Dijstra算法很像呢Σ(っ °Д °;)っ 。输入
每个测试点（输入文件）有且仅有一组测试数据。
在一组测试数据中：
第1行为1个整数N，表示小Hi拥有的城市数量。
接下来的N行，为一个N*N的矩阵A，描述任意两座城市之间建造道路所需要的费用，其中第i行第j个数为Aij，表示第i座城市和第j座城市之间建造道路所需要的费用。
对于100%的数据，满足N<=10^3，对于任意i，满足Aii=0，对于任意i, j满足Aij=Aji, 0<Aij<10^4.
输出
对于每组测试数据，输出1个整数Ans，表示为了使任意两座城市都可以通过所建造的道路互相到达至少需要的建造费用。
- 样例输入
50 1005 6963 392 1182 1005 0 1599 4213 1451 6963 1599 0 9780 2789 392 4213 9780 0 5236 1182 1451 2789 5236 0
- 样例输出
4178
#include <stdio.h>#include <string.h>#include <iostream>#include <string>#include <algorithm>#define INF 999999999#define N 1001using namespace std;int map[N][N];bool vis[N];int dis[N];int n, sum;void prim(){ sum=0; //最小生成树的权值和初始化0 int mm; int i, j; memset(vis, false, sizeof(vis)); for(i=0; i<n; i++) { dis[i]=map[0][i]; } vis[0]=true; int pos; for(i=0; i<n-1; i++) { mm=INF; for(j=0; j<n; j++) { if(vis[j]==false && dis[j]<mm) { mm=dis[j]; pos=j; } } sum+=mm; vis[pos]=true; for(j=0; j<n; j++) { if(vis[j]==false && dis[j]>map[j][pos] ) { dis[j]=map[j][pos]; } } } printf("%d\n", sum );}int main(){ int i, j; scanf("%d", &n); for(i=0; i<n; i++) { for(j=0; j<n; j++) { scanf("%d", &map[i][j] ); } } prim(); return 0;}
hihocoder hiho一下 第二十六周 最小生成树一·(Prim算法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。