蓝桥杯 城市建设 (Kruskal)
栋栋居住在一个繁华的 C 市中,然而,这个城市的道路大都年久失修。市长准备重新修一些路以方便市民,于是找到了栋栋,希望栋栋能帮助他。
C 市中有 n 个比较重要的地点,市长希望这些地点重点被考虑。现在可以修一些道路来连接其中的一些地点,每条道路可以连接其中的两个地点。另外由于 C 市有一条河从中穿过,也可以在其中的一些地点建设码头,所有建了码头的地点可以通过河道连接。
栋栋拿到了允许建设的道路的信息,包括每条可以建设的道路的花费,以及哪些地点可以建设码头和建设码头的花费。
市长希望栋栋给出一个方案,使得任意两个地点能只通过新修的路或者河道互达,同时花费尽量小。