题目：给出m条有向路，根不确定，求一棵最小的有向生成树。

分析：增加一个虚拟节点，连向n个节点，费用为inf（至少比sigma(cost_edge)大）。以该虚拟节点为根求一遍最小树形图算法，这时肯定存在解，如果费用>=inf时，说明无解。这是因为sigma(cost_edge)<inf。如何求得根？在寻找前驱时发现为根，则更新一下那条边的边号即可。

 

题目：n个地方需要供水，可以自己挖水井供给自己，或者可以从别的地方供水，给出各自的方案，问对n个城市供水的最小费用。

分析：由于可以自己供应给自己，题目显然有解。跟上题相似，添加一个虚拟节点，对n个城市连边，费用为自己供水的费用。对于n个城市之间的供水关系，直接建边。跑一次最小树形图算法即可。

 

代码略吧。。。