首页 > 其他分享 >南沙信息学家教陈老师: 1349:【例4-10】最优布线问题

南沙信息学家教陈老师: 1349:【例4-10】最优布线问题

时间:2024-08-28 17:07:24浏览次数:14  
标签:1349 计算机 nn 10 int 布线 数据线 连接 费用

【题目描述】

学校有nn台计算机,为了方便数据传输,现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同,因此不同的两台计算机的连接费用往往是不同的。

当然,如果将任意两台计算机都用数据线连接,费用将是相当庞大的。为了节省费用,我们采用数据的间接传输手段,即一台计算机可以间接的通过若干台计算机(作为中转)来实现与另一台计算机的连接。

现在由你负责连接这些计算机,任务是使任意两台计算机都连通(不管是直接的或间接的)。

【输入】

第一行为整数nn(2≤n≤1002≤n≤100),表示计算机的数目。此后的nn行,每行nn个整数。第x+1x+1行yy列的整数表示直接连接第xx台计算机和第yy台计算机的费用。

【输出】

一个整数,表示最小的连接费用。

【输入样例】

3
0 1 2
1 0 1
2 1 0

【输出样例】

2

【提示】

注:表示连接11和22,22和33,费用为22。

 

​
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
int g[101][101];
int n,ans=0;
struct Close {
	int adj;  //邻接点 
	int cost; //代价 
};
Close c[101];
int getMin()
{
	int min=INF,pos=0;
	for(int i=1;i<=n;i++)
	{
		if(c[i].cost!=0&&c[i].cost<min)
		{
			min=c[i].cost;
			pos=i;
		}
	}
	return pos;
}

void Prim(int u)
{
	for(int i=1;i<=n;i++)
	{
		if(i!=u)
		{
			c[i].adj=u;
			c[i].cost=g[u][i]; //存放连着U的顶点以及最小路径
		}
	}
	c[u].cost=0;  //初始U={u} 
	for(int i=1;i<=n;i++)
	{
		int pos=getMin();
		if(c[pos].adj!=0)
		{
			ans+=g[pos][c[pos].adj];
		}
		c[pos].cost=0; 
		for(int j=1;j<=n;j++)
		{
			if(c[j].cost!=0&&g[pos][j]<c[j].cost)
			{
				c[j].cost=g[pos][j];
				c[j].adj=pos;
			}
		}
	}
	
}
int main()
{
	memset(g,0x3f,sizeof(g));
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>g[i][j];
	Prim(1);
	cout<<ans;
	return 0;
}


​

 

标签:1349,计算机,nn,10,int,布线,数据线,连接,费用
From: https://www.cnblogs.com/nanshaquxinaosai/p/18385120

相关文章

  • QL5010-16-ASEMI逆变焊机专用整流桥QL5010
    编辑:llQL5010-16-ASEMI逆变焊机专用整流桥QL5010型号:QL5010品牌:ASEMI封装:KBPC-4批号:2024+类型:整流模块电流:50A电压:1600V安装方式:直插式封装特性:大功率、整流桥产品引线数量:4产品内部芯片个数:4产品内部芯片尺寸:MIL工作结温:-40℃~150℃功率:50W包装方式:500/盒:3000/箱......
  • P10785 [NOI2024] 集合
    思路:容易发现,区间\([l,r]\)中\(A\)与\(B\)等价的充分必要条为:两个序列中所有元素对于在区间\([l,r]\)内的出现集合组成的集合相等。这样才可以使得存在一种对应的映射方案使得等价。考虑哈希判定。设\(S_i\)表示\(i\)出现的位置的集合,则设\(\operatorname......
  • 【MySQL数据库管理问答题】第10章 选择备份策略
    目录1.请详细说明热备、温备和冷备的特点和不同。2.在MySQL中支持的备份类型有哪几种,分别予以说明。3.执行逻辑备份要具备哪些条件,其优缺点在哪。4.物理备份一般是用来满足什么样的数据库维护需求?5.基于快照的备份能否用来进行数据库损坏时的恢复,请说明理由。6.......
  • js的10个使用技巧
    js技巧01如果仅在变量为true的情况下调用函数,你就可以使用与(&&)的短路形式作为替代方法。 02如果期望值不正确,我们可以使用OR(丨丨)短路运算,为变量分配默认值。03将多个变量赋值我们可以通过数组解构来对一行中的多个变量赋值。 04箭头函数 05对于多值匹配来......
  • 达梦数据库在Delphi10.3上的安装与连接
          ......
  • 基于stm32f103c8t6的智能蓝牙遥控小车(有代码)
    智能小车对于初学者而言还是有点挑战性的,由于本人一直以来都在专注于学业绩点,很少有时间来学习stm32,但这学期开始课慢慢的变少,所以又开始学习32顺便做一些小项目,本文将以stm32为核心制作蓝牙遥控小车。之后我也会继续发一些其他的小项目资料和经验总结。所需材料:12v的电源3......
  • Waymo新增第二座机器人出租车装配厂,周载客量突破10万次
    数十辆Waymo自动驾驶汽车停放在旧金山的一个集结区内。据《福布斯》了解,Waymo正与汽车工程公司Magna合作,在亚利桑那州开设第二个组装设施。该工厂将为该公司快速扩张的一部分,配备数千辆电动捷豹SUV。Waymo向《福布斯》确认,新工厂位于亚利桑那州的梅萨,由Magna负责运营,将根据合......
  • 109.微软邮箱强制要求使用MS Authenticator手机APP但中国没有GooglePlay的处理办法
    109.微软邮箱强制要求使用MSAuthenticator手机APP但中国没有GooglePlay的处理办法  背景: 微软邮箱强制用户使用它的Authenticator手机验证器APP(只能跳过3次), 而大部分中国用户手机上是没有谷歌框架和GooglePlay的,所以导致很多用户无法使用微软企业邮箱微软自己也发现了......
  • 怎么永久禁止win10系统自动更新,想关闭电脑更新怎么办呢
    永久禁止Windows10系统自动更新的方法有多种,以下是几种常见且有效的办法:通过服务管理器禁用WindowsUpdate服务步骤:按下Win+R键,输入services.msc,然后按Enter键打开服务管理器。在服务列表中滚动查找“WindowsUpdate”服务。右键点击“WindowsUpdate”服务,选择“属性......
  • win10的自动更新在哪,怎么打开电脑更新设置
    在Windows10系统中,自动更新的设置位置相对直观,用户可以按照以下步骤找到并配置自动更新设置:一、通过设置界面找到自动更新1.打开设置:点击屏幕左下角的“开始”按钮,然后选择“设置”(齿轮形状的图标)或者直接按下Win+I快捷键打开设置应用。2.进入更新和安全:在设置窗口中,找到并......