中国建设银行官网站住房公积金,python创建网站,网络公司网站源码,靖江做网站的单位题目大意#xff1a; 给n个节点#xff0c;m条边#xff0c;问最小生成树#xff0c;次小生成树#xff1f; ps#xff1a;以前做次小生成树的时候估计没有掌握牢固#xff0c;这次wa的好辛苦哟。 1 #include cmath2 #include queue3 #include stri…题目大意 给n个节点m条边问最小生成树次小生成树 ps以前做次小生成树的时候估计没有掌握牢固这次wa的好辛苦哟。 1 #include cmath2 #include queue3 #include string4 #include cstdio5 #include cstring6 #include iostream7 #include algorithm8 using namespace std;9
10 const int maxn 100;
11 const int INF 0x3f3f3f3f;
12 const double Exp 1e-10;
13
14 int cost[maxn10][maxn10], lowc[maxn10], vis[maxn10];
15 int Max[maxn10][maxn10], used[maxn10][maxn10], pre[maxn10];
16 int n;
17 void init ()
18 {
19 for (int i1; in; i)
20 for (int j1; jn; j)
21 if (i j)
22 cost[i][j] 0;
23 else
24 cost[i][j] INF;
25 }
26 int prim ()
27 {
28 int i, j, sum 0;
29 memset (Max, 0, sizeof(Max));
30 memset (used, 0, sizeof(used));
31 memset (vis, 0, sizeof(vis));
32 vis[1] 1;
33 for (i1; in; i)
34 {
35 lowc[i] cost[1][i];
36 pre[i] 1;
37 }
38 for (i1; in; i)
39 {
40 int p, mini INF;
41 for (j1; jn; j)
42 if (!vis[j] mini lowc[j])
43 {
44 p j;
45 mini lowc[j];
46 }
47 vis[p] 1;
48 sum mini;
49 used[pre[p]][p] used[p][pre[p]] 1;
50 for (j1; jn; j)
51 {//这一点的错误wa的好苦
52 if (vis[j] j ! p)//p!j一定要有否则Max[i][i]的距离就可能会不等于零影响后面的计算过程
53 Max[j][p] Max[p][j] max(Max[j][pre[p]], lowc[p]);
54 if (!vis[j] lowc[j] cost[p][j])
55 {
56 lowc[j] cost[p][j];
57 pre[j] p;
58 }
59 }
60 }
61 return sum;
62 }
63 int smst (int sum)
64 {
65 int i, j, mini INF;
66 for (i1; in; i)
67 for (ji1; jn; j)
68 if (cost[i][j] ! INF !used[i][j])
69 mini min (mini, sum cost[i][j] - Max[i][j]);
70 return mini;
71 }
72 int main ()
73 {
74 int t, m;
75 scanf (%d, t);
76 while (t --)
77 {
78 scanf (%d %d, n, m);
79 init ();
80 while (m --)
81 {
82 int a, b, c;
83 scanf (%d %d %d, a, b, c);
84 cost[a][b] cost[b][a] c;
85 }
86 int num1, num2;
87 num1 prim ();
88 num2 smst (num1);
89 printf (%d %d\n, num1, num2);
90 }
91 return 0;
92 } 转载于:https://www.cnblogs.com/alihenaixiao/p/4549538.html
