与此同时,K国正筹备国王女儿的婚礼。然而,为了不在亲戚们的前丢脸,国王必须先完成国内的改革。由于国王已经急不可耐,改革必须尽快完成。
该王国目前由n座城市组成。这些城市通过n-1条双向道路相连,确保任意城市间均可通行。由于国王需要节省开支,任意两座城市之间仅有一条路径。
改革的意义何在?国家的关键部门应当迁移至不同的城市(我们称之为重要城市)。然而,由于面临蛮族攻击的高风险,此事必须谨慎推进。国王已制定多套方案,每套方案都由一组重要城市构成,现正思索最佳方案。
蛮族可以攻占一些不重要的城市(重要的城市肯定会有足够的防御),攻占后该城市将无法通行。计划的一个特征在于蛮族需要攻占的最少城市数量,以使所有重要城市彼此孤立,即从任何重要城市都无法抵达其他重要城市。
帮国王计算出他每个计划的这一特征。