本文摘要：这篇文章描述了作者在解决一道最小生成树问题时的经历。采用C++实现Prim算法过程中，作者遭遇了WA（错误答案）的困境，在历经调试后发现并修复了一个关键bug。最终成功AC（正确答案），实现了经典的Prim算法求解图论问题。文章详细记录了如何通过不断优化代码和深入理解算法，逐步解决在线判题系统中的题目，尤其强调了处理边权值及更新顶点集合状态在实现过程中的重要性。

转载文章

本篇文章为转载内容。原文链接：https://blog.csdn.net/weixin_30239339/article/details/96526588。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

发现前面有一堆类似dfs的题目，做多了有点烦，就直接跳到后面看看，发现这题最小生成树，刚好前几天看书看到，就拿来做做，但很不顺利的wa了，找了很久bug也不知道。终于在某次中发现了，原来我直接用x了，竟然能对6个case，可怕！改了后果断ac，经典prim算法，我就不说了，自己看书去。

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<stdlib.h>
 5 #define max(a,b) a>b?a:b
 6 #define min(a,b) a>b?b:a
 7 #define INF     0x3f3f3f3f
 8 #define Maxin 10000
 9 int fang[4][2]={{-1,0},{1,0},{0,-1},{0,1} };
10 int map[105][105],n;
11 int in[105],inn=0,notin[105];//in是已经被用过的点，notin是还没用的点
12 int get()
13 {
14    int x,ans=INF;
15    int ay;
16    for(x=0;x<inn;x++)//在已经用的点里找一个距离最小的边来用
17        {
18            int y;
19            for(y=0;y<n;y++)
20              if(notin[y]!=-1&&map[in[x]][y]<ans&&in[x]!=y)//notin！=-1表示还没被用
21              {
22                  ans=map[in[x]][y];
23                  ay=y;
24              }
25        }
26        in[inn++]=ay;
27        notin[ay]=-1;
28        return ans;
29 }
30 
31 int main()
32 {
33     int x,y,ans=0;
34     scanf("%d",&n);
35     for(x=0;x<n;x++)
36     {
37         for(y=0;y<n;y++)
38         scanf("%d",&map[x][y]);
39         notin[x]=x;
40     }
41     in[inn++]=0;
42     notin[0]=-1;
43     while(inn!=n)
44     ans+=get();
45     printf("%d\n",ans);
46     return 0;
47 }

转载于:https://www.cnblogs.com/usp10/archive/2012/05/26/2519690.html

本篇文章为转载内容。原文链接：https://blog.csdn.net/weixin_30239339/article/details/96526588。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

名词解释

作为当前文章的名词解释，仅对当前文章有效。

最小生成树：在图论中，最小生成树是指在一个带权重的无向连通图中，找到一棵包括所有顶点且总权重最小的树。在这篇文章中，作者通过Prim算法来求解最小生成树问题，即从图中的一个顶点开始，逐步添加边，确保每一步添加的边都不会形成环路，直到所有顶点都被包含在内，并使得最终形成的树的所有边的权值之和达到最小。

Prim算法：Prim算法是解决图论中最小生成树问题的一种贪心策略算法，由捷克数学家Vojtěch Jarník于1930年提出，后被美国计算机科学家Robert C. Prim独立发现并推广。在该文章的具体情境下，作者使用C++编程语言实现了Prim算法，其基本思想是从图中的一个顶点出发，每次从未加入到生成树中的顶点集中选取与已加入顶点集相连且权值最小的边，将其对应的顶点加入生成树，重复此过程直至所有顶点均被包含在生成树中。

在线判题系统：在线判题系统是一种自动化评测平台，广泛应用于编程竞赛、课程作业等场景，可以自动接收用户提交的代码，运行测试用例并对结果进行评判。本文中提到的作者在解决最小生成树问题时，就是在这样的在线判题系统上调试和提交代码，经历从WA（错误答案）到AC（正确答案）的过程，表明其解决方案得到了系统的认可。