不定根专题

kuangbin专题八 HDU2121 Ice_cream’s world II(不定根的最小树形图)

题意: 一个国家有N个城市,M条有向道路,女王想要选一个城市为首都,使得这个城市既能连接所有的城市,而且总的路程最短。若能找到这个城市,则输出最短路程和最小的城市编号。 题解: 最小树形图+超级源点,因为是不定根,我一开始是想暴力枚举的,然后发现复杂度爆炸了,就放弃了,后来才知道这道题可以用超级源点,怎么用超级源点呢?如果要用超级源点的话,肯定得在用完它之后删除掉这个点和与它有关的边之后对图