HDU1863---最小生成树（prim算法）

╰+哭是因爲堅強的太久メ 2022-08-27 06:52 171阅读 0赞

/\*最小生成树基本算法HDU 1863\*/  
\# include<iostream>  
\# include<algorithm>

using namespace std;

const int N=205;  
const int INF=1000000000;  
int g\[N\]\[N\];  
int dis\[N\],n,m;  
bool flag\[N\];  
int Prim()  
\{

int mincost=0;

for(int i=1;i<=n;i++)  
\{

flag\[i\]=0;//首先对其标记数组进行全部初始化为0，也就表明此时的集合中没有一个元素

dis\[i\]=INF;//对距离数组都进行初始化为无穷大，也就是表明此时顶点到任何点的距离都为无穷大

\}

for(int i=2;i<=n;i++)

dis\[i\]=g\[1\]\[i\];//把顶点为编号1到邻近的点的距离存在dis数组中

flag\[1\]=1;dis\[1\]=0;//把第一个点放入集合中（flag\[1\]=1;），表示此时集合中只有顶点1一个元素，dis\[1\]=0,表示顶点到本身的距离为0；

for(int t=1;t<n;t++)  
\{

int mindis=INF,idx=-1;//定义一个赋初值为无穷大的变量，为了就是比较出最短的距离，用idx变量标记下标

for(int i=1;i<=n;i++)

if(!flag\[i\]&&mindis>dis\[i\])//!flag\[i\]表示把没有加入集合元素的点进行比较，而已经加入集合的点就不能；

\{mindis=dis\[i\];idx=i;\}//表示把其中最小的距离找到，并把其最小距离的下标，赋给idx

if(idx==-1) return -1;//表示如果没有以上条件的，idx的原值不变还是-1，所以就返回-1；

mincost+=dis\[idx\];//dis\[idx\]存放的都是符合条件的最短的距离，然后进行累加，最终mincost得到的将是最短距离的总和，也是最少的花费

flag\[idx\]=1;//把符合条件的点放入集合中，也就是更新点

for(int i=1;i<=n;i++)

if(!flag\[i\])//把还没有放入集合的点，进行接下来比较

if(dis\[i\]>g\[idx\]\[i\])//表示从那个刚更新的点的整个集合为起点开始，接着找出最短距离的点，直到全部都找完为止

dis\[i\]=g\[idx\]\[i\];//并把最短距离存下来。  
\}  
return mincost;  
\}  
int main()  
\{  
while(cin>>m>>n)  
\{

if(m==0) break;

for(int i=1;i<=n;i++)

for(int j=1;j<=n;j++)

g\[i\]\[j\]=INF;

while(m--)  
\{

int u,v,w;

cin>>u>>v>>w;

g\[u\]\[v\]=min(g\[u\]\[v\],w);

\}

int mincost=Prim();

if(mincost==-1) cout<<"?"<<endl;

else cout<<mincost<<endl;

\}  
return 0;  
\}

发表评论取消回复

表情：

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

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

相关阅读

相关 HDU 1102 Constructing Roads （最小生成树 Prim算法）

Constructing Roads Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K

女爷i/ 2024年02月18日 16:39/ 0 赞/ 51 阅读

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

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

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

相关最小生成树之prim算法

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

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

相关 HDU1863---最小生成树（prim算法）

/\最小生成树基本算法HDU 1863\/ \ include<iostream> \ include<algorithm> using namespace s

╰+哭是因爲堅強的太久メ/ 2022年08月27日 06:52/ 0 赞/ 172 阅读

相关 hdoj 1863 畅通工程【最小生成树，kruskal&&prim】

畅通工程 Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

水深无声/ 2022年08月04日 12:45/ 0 赞/ 166 阅读

相关最小生成树prim算法

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

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

相关最小生成树-Prim算法

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

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

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

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

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

相关最小生成树(Kruskal)HDU 1863-畅通工程

最小生成树(Kruskal)HDU 1863-畅通工程 -------------------- 题目链接： [畅通工程][Link 1]

蔚落/ 2022年05月15日 06:44/ 0 赞/ 225 阅读

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

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

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