当当当~
又到了解疑的时候啦~
今天给小伙伴们讲一下
最小生成树(Prim算法)
首先我们来看一下题目
题目描述
学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，任务是使任意两台计算机都连通（不管是直接的或间接的）。
第一行为整数n（2≤n≤），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
一个整数，表示最小的连接费用。
3
2
注：表示连接1和2，2和3，费用为2。
解题思路
核心思路：最小生成树+Prim算法
-以1为起点的最小生成树，min[v]表示蓝点v与白点相连的最小边权
-MST表示最小生成树的权值之和
-初始化:min[v]极大值，min[1]=0,MST=0;
-for(i=1;i=n;i++)
{
寻找min最小的蓝点u
将u标记为白点
MST+=min
for与白点u相连的所有蓝点v
if(w[v]min[v])min[v]=w[v];
}
-MST即最小生成树权值之和
下面是参考代码~
"#includebits/stdc++.h
usingnamespacestd;
intg[][],minn[];
boolu[];
intn;
intmain()
{
cinn;
for(inti=1;i=n;i++)
for(intj=1;j=n;j++)
cing[j];
memset(minn,0x7f,sizeof(minn));
minn[1]=0;
for(inti=1;i=n;i++)
{
intk=0;
for(intj=1;j=n;j++)
{
if(u[j]==0(minn[j]minn[k]))
k=j;
}
u[k]=1;
for(intj=1;j=n;j++)
{
if(u[j]==0(g[k][j]minn[j]))
minn[j]=g[k][j];
}
}
inttotal=0;
for(inti=1;i=n;i++)
total+=minn;
couttotal;
}
"▼
点击了解更多详情
▼
成绩展示
喜报
CCFCSP-J/S第二轮认证评级，机房日子编程再创佳绩!
年NOI与NOIP获奖学员公示！新的一年我们再次出发！
机房课程
暑期课程
一对一课程，量身定制！
课程
线上一对一课程，为你量身定制!
搜索基础课程与动态规划基础课程
算法与数据结构专题课
NOIP数学专题课
《动态规划》特设专题课
机房解疑
机房解疑
杨辉三角形
机房解疑
迪杰斯特拉算法
机房解疑
Floyed(弗洛伊德)算法
机房解疑
哈密尔顿环
机房解疑
不等数列
机房解疑
记数问题
机房解疑
进制转换
机房解疑
四方定理
机房解疑
最大正方形
机房解疑
欧拉路
机房解疑
一元三次方程求解
机房解疑
装箱问题
机房解疑
均分纸牌
机房解疑
排队接水
机房解疑
货币系统
机房解疑
喝醉的狱卒
机房解疑
完全背包
机房解疑
01背包
机房解疑
合并石子（直线问题）
机房解疑
黑白棋子的移动
机房解疑
N皇后
机房解疑
逆序对
机房解疑
归并排序
机房解疑
快速排序
机房解疑
约瑟夫问题-猴子选大王
机房解疑
递归-汉诺塔问题
机房解疑
搜索-全排列
机房解疑
高精度运算，不简单的A+B
机房分享
机房分享
多省市高中特长生招生计划公布，注重“信息学特长生”选拔
机房分享
强基时代来了！知名中学纷纷开设“强基班”，是啥信号？
机房分享
信息学奥赛的10大误区
机房分享
送给NOIP竞赛学生的几条建议！
机房分享
五大学科竞赛到底能给我们带来什么？
机房分享
信息学奥赛（NOIP）复赛学习方法与备考攻略
机房分享
新手入门信息学奥赛（NOIP）常见问题解答
机房分享
高考数学再现编程题！
扫描下方