h5科技 网站,网站建设必须安装程序,wordpress远程图片模块,医院网站必须建设吗Highways大意#xff1a;给你一个用邻接矩阵形式存储的有n个顶点的无向图#xff0c;让你求它的最小生成树并求出在这个生成树里面最大的边的权值。 思路#xff1a;用Prim求#xff0c;判断条件改一下就行。 PS#xff1a;dis数组初始化的时候用memset一直RE#xff0c;…Highways 大意给你一个用邻接矩阵形式存储的有n个顶点的无向图让你求它的最小生成树并求出在这个生成树里面最大的边的权值。 思路用Prim求判断条件改一下就行。 PSdis数组初始化的时候用memset一直RE希望有知道怎么回事的不吝赐教谢了~ 1 #include stdio.h2 #include string.h3 #define INF 0x3f3f3f3f4 5 int Map[510][510];6 int dis[510];7 int n, m;8 9 int min(int a, int b)
10 {
11 return a b ? b : a;
12 }
13
14 int Prim()
15 {
16 int Min_ele, Min_node;
17 for(int i 1; i n; i)
18 {
19 dis[i] INF;
20 }
21 ///这里如果用memset(dis, INF, sizeof(dis));的话会一直RE
22 int r 1;
23 int Ans 0;
24 for(int i 1; i n; i)
25 {
26 Min_ele INF;
27 dis[r] -1;
28 for(int j 1; j n; j)
29 {
30 if(j ! r dis[j] 0)
31 {
32 dis[j] min(dis[j], Map[r][j]);
33 if(dis[j] Min_ele)
34 {
35 Min_ele dis[j];
36 Min_node j;
37 }
38 }
39 }
40 r Min_node;
41 if(Min_ele Ans)
42 Ans Min_ele;
43 }
44 return Ans;
45 }
46
47 void Solve()
48 {
49 scanf(%d, m);
50 while(m--)
51 {
52 scanf(%d, n);
53 memset(Map, 0, sizeof(Map));
54 for(int i 1; i n; i)
55 {
56 for(int j 1; j n; j)
57 {
58 scanf(%d, Map[i][j]);
59 }
60 }
61 printf(%d\n, Prim());
62 }
63 }
64
65 int main()
66 {
67 Solve();
68
69 return 0;
70 } Highways 转载于:https://www.cnblogs.com/Silence-AC/p/3531342.html
