ssl 1764 1682 USACO 3.1 Agri-Net 最短网络 (最小生成树)#prim#_lemondinosaur的博客-程序员秘密

技术标签：最小生成树 ssl 1764 USACO 3.1 ssl 1682 Agri-Net

###题意：求最小生成树的权值和。

#include <cstdio>
#include <cctype>
#include <climits>
using namespace std;
int a[101][101],lowcost[101]; bool v[101];
inline int in(){
	char x=getchar(); int ans=0;
	while (!isdigit(x)) x=getchar();
	while (isdigit(x)) ans=ans*10+x-48,x=getchar();
	return ans;
}
int main(){
	int n,k,min,s=0; n=in();
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++) a[i][j]=in();
		lowcost[i]=a[1][i];//从第一个点到其他点的最小值
	} v[1]=1;
	for (int i=1;i<=n-1;i++){
		min=INT_MAX;
		for (int j=1;j<=n;j++)
		if (lowcost[j]<min&&!v[j]){//求最小值
			min=lowcost[j];
			k=j;
		}
		s+=min;
		v[k]=1;//加入集合
		for (int j=1;j<=n;j++) if (a[k][j]<lowcost[j]) lowcost[j]=a[k][j];//更新最小值
	}
	printf("%d",s); return 0;
}

本文链接：https://blog.csdn.net/sugar_free_mint/article/details/78987727

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

vue element中引入阿里巴巴矢量图标库_element中引入矢量图_maybe28的博客-程序员秘密

选择好自己想要的图标加入购物车，添加至自己的某一个项目中。️在更多操作中，我们需要对项目进行一个编辑。这里的设置主要是为了不和element的图标冲突。然后下载到本地之后，放在src／assets下。在iconfont.css中进行修改。增加一段如图所示的代码：[class^="el-icon-ump"], [class*=" el-icon-ump"] { font-...

红米Note 5详细卡刷开发版获得root超级权限的步骤_weixin_33749242的博客-程序员秘密

小米的机器不同手机型号一般情况下miui论坛都提供两个不同版本，大概分为稳定版和开发版，稳定版没有提供ROOT权限管理，开发版中就支持了ROOT权限，很多时候我们需要使用的一些功能强大的APP，都需要在ROOT权限下工作，比如我们单位在使用的营销引流APP引号精灵，就是需要有ROOT权限才能进行正常启动，但很多时候，我们新买到的手机一般情况下默认安装的是小米系统的稳定版，这个时候我们需要将红米No...

vc6.0 调试程序，终止调试时程序却无法退出_Fly-Skyline的博客-程序员秘密

详情描述：在使用vc6.0（系统：windows 7 64 bit）调试程序时遇到终止调试时，程序无法退出的情况。由于无法直接关闭调试程序的进程，

Java8 新特性之流式数据处理_summarizingdouble_六芒兎的博客-程序员秘密

Java8 新特性之流式数据处理

Kibana之Console介绍_weixin_34221073的博客-程序员秘密

2019独角兽企业重金招聘Python工程师标准>>> ...

确定权重的方法-主成分分析_主成分分析如何确定主成分_bingbangx的博客-程序员秘密

什么是权重呢？所谓权重，是指某指标在整体评价中的相对重要程度。权重越大则该指标的重要性越高，对整体的影响就越高。权重要满足两个条件：每个指标的权重在0、1之间。所有指标的权重和为1。权重的确定方法有很多，这里我们学习用主成分分析确定权重。一、主成分基本思想：图1 主成分基本思想的问与答二、利用主成分确定权重如何利用主成分分析法确定指标权重呢？现举例说明。假设我们对反映某卖场表现的4项指标（实体...