HBC237204[ZJOI2016]旅行者,最短路,分治,图论拯救萝莉(hard version)题解

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

本题有对应的easyversion，区别仅在于easy version多一个额外限制条件，见输入描述，保证easy version的测试用例集是hardversion的子集， 注意hard version中有额外样例， 邪恶的魔王抓走了所有的小萝莉，并且把她们关在了NNN个城堡中，不过好消息是，清楚姐姐现在已经占领了111号城堡，并且在城堡中训练一些士（群）兵（友）来作战，

本题有对应的easy version，区别仅在于easy version多一个额外限制条件，见输入描述，保证easy version的测试用例集是hard version的子集。 注意hard version中有额外样例。 邪恶的魔王抓走了所有的小萝莉，并且把她们关在了NNN个城堡中，不过好消息是，清楚姐姐现在已经占领了111号城堡，并且在城堡中训练一些士（群）兵（友）来作战。 城堡与城堡之间有MMM条单向运兵线路，清楚姐姐只能按照这些单向道路派兵攻打敌方城堡。 这NNN个城堡的分布结构呈一张有向无环图（DAG）的结构，并且保证从111号城堡出发可以通过单向道路到达其他N−1N-1N−1个城堡中。 对于除了111号城堡以外的每一个城堡，都被大魔王控制，每一座城堡有三个属性：防御力DDD，敌人总数AAA，以及人口数PPP。 清楚姐姐在任意时刻都可以进行如下几个操作 移动：清楚姐姐可以命令自己的士兵按照城堡间的单向道路移动，前提是单向道路两端的城堡均已被清楚姐姐控制或为中立状态。 攻击：清楚姐姐可以选择一个敌方控制的目标城堡，以及若干个己方已控制且可直接通过运兵路线攻击目标的城堡发动一次攻击，攻击所需的兵力由这若干个城堡随意分配，每次进攻时，若干个己方城堡用于进攻的兵力总和SSS不得少于DDD，我方士兵与敌方死战。                     若SAS>AS>A则战斗结束后目标城堡中我方士兵剩余S−AS-AS−A，全歼敌人，可以直接进行“占领”操作。 占领：当我方战斗结束全歼敌人且至少有111人存活，或者往中立城堡派出111个士兵后，可以进行占领，占领后该城堡变为我方控制状态，且最多可以招募PPP人成为我方士兵，新招募的士兵初始位置位于该占领的城堡。对于已经占领的城堡，可以将所有士兵都调走，即使所有士兵都离开也不会转化为中立状态。 招募：除了一开始的111号城堡以外，每一个我方控制的城堡都可以最多招募不多于该城堡人口上限PPP的士兵。 为了拯救小萝莉，清楚姐姐需要占领其余N−1N-1N−1个城堡。 现在智乃想知道，清楚姐姐一开始在111号城堡中训练多少群友才能达成目标。 有向无环图oi-wiki：https://oi-wiki.org/graph/dag/ 牛客竞赛图论课程：https://ac.nowcoder.com/courses/cover/live/740 不会做说明该买课了（

全网最全C++题库，助您挑战自我，突破极限，成为编程领域的佼佼者！

标签： HBC237204[ZJOI2016]旅行者 最短路 分治 图论拯救萝莉(hard version)题解