题号:NC237204
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld
题目描述
本题有对应的easy version,区别仅在于easy version多一个额外限制条件,见输入描述,保证easy version的测试用例集是hard version的子集。
注意hard version中有额外样例。
邪恶的魔王抓走了所有的小萝莉,并且把她们关在了

个城堡中,不过好消息是,清楚姐姐现在已经占领了

号城堡,并且在城堡中训练一些士(群)兵(友)来作战。
城堡与城堡之间有

条单向运兵线路,清楚姐姐只能按照这些单向道路派兵攻打敌方城堡。
这

个城堡的分布结构呈一张有向无环图(DAG)的结构,并且保证从

号城堡出发可以通
过单向道路到达其他

个城堡中。
对于除了

号城堡以外的每一个城堡,都被大魔王控制,每一座城堡有三个属性:防御力

,敌人总数

,以及人口数

。
清楚姐姐在任意时刻都可以进行如下几个操作
- 移动:清楚姐姐可以命令自己的士兵按照城堡间的单向道路移动,前提是单向道路两端的城堡均已被清楚姐姐控制或为中立状态。
- 攻击:清楚姐姐可以选择一个敌方控制的目标城堡,以及若干个己方已控制且可直接通过运兵路线攻击目标的城堡发动一次攻击,攻击所需的兵力由这若干个城堡随意分配,每次进攻时,若干个己方城堡用于进攻的兵力总和
不得少于
,我方士兵与敌方死战。
若

则战斗结束后目标城堡的敌人总数变为

,我方参与本场战斗的士兵全部战死。
若

则战斗结束后目标城堡中我方士兵与敌方士兵全部阵亡,城堡处于无人的中立状态。
若

则战斗结束后目标城堡中我方士兵剩余

,全歼敌人,可以直接进行“
占领”操作。
- 占领:当我方战斗结束全歼敌人且至少有
人存活,或者往中立城堡派出
个士兵后,可以进行占领,占领后该城堡变为我方控制状态,且最多可以招募
人成为我方士兵,新招募的士兵初始位置位于该占领的城堡。对于已经占领的城堡,可以将所有士兵都调走,即使所有士兵都离开也不会转化为中立状态。 - 招募:除了一开始的
号城堡以外,每一个我方控制的城堡都可以最多招募不多于该城堡人口上限
的士兵。
为了拯救小萝莉,清楚姐姐需要占领其余

个城堡。
现在智乃想知道,清楚姐姐一开始在

号城堡中训练多少群友才能达成目标。
不会做说明该买课了(
输入描述:
第一行输入两个正整数
)
表示城堡的数目

以及单向运兵路线的数目

。
接下来

行,每行输入三个非负整数
)
表示从

号城堡到

号城堡的防御力

,敌人总数

,以及人口数

。
接下来

行,每行输入两个正整数
)
表示一条单向运兵线路。
输入保证这些运兵线路构成一个DAG图,且从

号城堡可到达所有城堡。
输出描述:
仅一行一个整数,表示清楚姐姐一开始在
号城堡中训练多少群友才能达成目标。
示例1
输入
复制
3 2
0 1 99
100 100 0
1 2
2 3
说明
一开始训练

名群友,派它们攻击

号城堡。

号城堡的防御力为

,所以可以派

名群友直接进攻该城堡。
战斗结束后,在

号城堡内我方剩余

名士兵,占领

号城堡并招募

人,此时城堡内有

人。
最后派

人攻击

号城堡,在

号城堡内我方剩余

名士兵,占领该城堡获得胜利。
示例2
说明
城堡的防御力为
,需要至少
人同时进攻才能攻打城堡。
示例3
说明
注意至少需要
人存活才能占领城堡。
示例4
输入
复制
10 9
5 7 6
0 9 5
9 2 2
8 7 9
10 2 0
4 3 5
4 10 8
9 8 8
1 2 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
示例5
输入
复制
4 4
60 50 100
50 60 100
210 210 0
1 2
1 3
2 4
3 4
说明
注意可以同时选中多个已经占领的城堡,合力进攻。
一开始在

号城堡招募

名群友,派

人攻打

号城堡,派

人攻打

号城堡。
攻打之后立刻进行招募,此时

号城堡内有

人,

号城堡内有

人、
选中

号,

号城堡合力共

人进攻

号城堡成功占领所有城堡。
示例6
输入
复制
12 15
93474 10128 65752
65221 6983 41034
82452 34722 48764
21423 41519 59398
760 34788 24645
51178 9985 15211
52050 76240 64792
20318 16102 23494
90614 48972 68565
4694 22617 70520
76983 90440 76132
1 2
8 9
1 4
1 10
1 3
1 4
4 5
1 10
5 11
11 12
4 6
6 7
7 8
1 9
3 6
备注:
有向无环图oi-wiki:https://oi-wiki.org/graph/dag/
牛客竞赛图论课程:https://ac.nowcoder.com/courses/cover/live/740
不会做说明该买课了(