贪心嘛~ 因为一共 \(p\) 个点, 所以在 \(MST\) 中只有 \(p-1\) 条边; 同理, \(s\) 部卫星电话, 可以照顾 \(s-1\) 条边, 那就 Kruskal 最后的 \(s-1\) 条边用卫星电话相连.
所以,当计数器 <code>cnt</code> 计到 大于等于 \((p-1)-(s-1)=p-s\) 时,就停下来, 输出边权就行了
贪心嘛~ 因为一共 \(p\) 个点, 所以在 \(MST\) 中只有 \(p-1\) 条边; 同理, \(s\) 部卫星电话, 可以照顾 \(s-1\) 条边, 那就 Kruskal 最后的 \(s-1\) 条边用卫星电话相连.
所以,当计数器 <code>cnt</code> 计到 大于等于 \((p-1)-(s-1)=p-s\) 时,就停下来, 输出边权就行了
![POJ 1284 Primitive Roots (欧拉函数&原根定理)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)