|
Min = INF;
19 for(j = 1; j <= n; j++) if(!vis[j] && key[j] < Min) {
20 Mini = j; //找key值最小的点，即与树相邻的节点的最小权值边
21 Min = key[j];
22 }
23 vis[Mini] = 1; //设置访问过，即生成树已连接Mini这个节点
24 ans += key[Mini];
25 if(key[Mini]) {
26 f[m] = min(p[Mini], Mini); //字典序的边
27 l[m++] = max(p[Mini], Mini); //同上
28 }
29 for(j = 1; j <= n; j++) //伪松弛，更新树临边节点的key值并维护p域
30 if(!vis[j] && edge[Mini][j] < key[j]) {
31 key[j] = edge[Mini][j];
32 p[j] = Mini;
33 }
34 }
35 cout << m << endl;
36 for(i = 0; i < m; i++) cout << f[i] << ' ' << l[i] << endl;
37 cout << ans;
38 return 0;
39 }
|