列表

详情

NC237202. 拯救萝莉(easy version)

描述

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

城堡与城堡之间有M条单向运兵线路，清楚姐姐只能按照这些单向道路派兵攻打敌方城堡。
这N个城堡的分布结构呈一张有向无环图（DAG）的结构，并且保证从1号城堡出发可以通过单向道路到达其他N-1个城堡中。

对于除了1号城堡以外的每一个城堡，都被大魔王控制，每一座城堡有三个属性：防御力D，敌人总数A，以及人口数P。

清楚姐姐在任意时刻都可以进行如下几个操作
  • 移动：清楚姐姐可以命令自己的士兵按照城堡间的单向道路移动，前提是单向道路两端的城堡均已被清楚姐姐控制或为中立状态。
  • 攻击：清楚姐姐可以选择一个敌方控制的目标城堡，以及若干个己方已控制且可直接通过运兵路线攻击目标的城堡发动一次攻击，攻击所需的兵力由这若干个城堡随意分配，每次进攻时，若干个己方城堡用于进攻的兵力总和S不得少于D，我方士兵与敌方死战。
                    若则战斗结束后目标城堡的敌人总数变为A-S，我方参与本场战斗的士兵全部战死。
                    若则战斗结束后目标城堡中我方士兵与敌方士兵全部阵亡，城堡处于无人的中立状态。
                    若则战斗结束后目标城堡中我方士兵剩余S-A，全歼敌人，可以直接进行“占领”操作。
  • 占领：当我方战斗结束全歼敌人且至少有1人存活，或者往中立城堡派出1个士兵后，可以进行占领，占领后该城堡变为我方控制状态，且最多可以招募P人成为我方士兵，新招募的士兵初始位置位于该占领的城堡。对于已经占领的城堡，可以将所有士兵都调走，即使所有士兵都离开也不会转化为中立状态。
  • 招募：除了一开始的1号城堡以外，每一个我方控制的城堡都可以最多招募不多于该城堡人口上限P的士兵。
为了拯救小萝莉，清楚姐姐需要占领其余N-1个城堡。
现在智乃想知道，清楚姐姐一开始在1号城堡中训练多少群友才能达成目标。

有向无环图oi-wiki：https://oi-wiki.org/graph/dag/
牛客竞赛图论课程：https://ac.nowcoder.com/courses/cover/live/740

输入描述

第一行输入两个正整数表示城堡的数目N以及单向运兵路线的数目M。
接下来N-1行，每行输入三个非负整数表示从2号城堡到N号城堡的防御力D，敌人总数A，以及人口数P。
接下来M行，每行输入两个正整数表示一条单向运兵线路。
输入保证这些运兵线路构成一个DAG图，且从1号城堡可到达所有城堡。
easy version额外限制：保证且对于，城堡i到城堡必定存在运兵路线。

输出描述

仅一行一个整数，表示清楚姐姐一开始在1号城堡中训练多少群友才能达成目标。

示例1

输入: 

3 2
0 1 99
100 100 0
1 2
2 3

输出: 

3

说明:

一开始训练3名群友，派它们攻击2号城堡。2号城堡的防御力为0，所以可以派3名群友直接进攻该城堡。
战斗结束后，在2号城堡内我方剩余2名士兵，占领2号城堡并招募99人，此时城堡内有101人。
最后派101人攻击3号城堡，在3号城堡内我方剩余1名士兵，占领该城堡获得胜利。

示例2

输入: 

2 1
100 1 0
1 2

输出: 

100

说明:

城堡的防御力为100，需要至少100人同时进攻才能攻打城堡。

示例3

输入: 

2 1
1 100 0
1 2

输出: 

101

说明:

注意至少需要1人存活才能占领城堡。

示例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

输出: 

14

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 5ms, 内存消耗: 428K, 提交时间: 2022-06-01 20:39:14 

#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,m,sum=0,q=0;
	cin>>n>>m;
	for(int i=2;i<=n;i++){
		long long int x,y,z;
		cin>>x>>y>>z;
		if(q<x){
			sum=sum+x-q;
			q=x;
		}
		if(q>=y){
			q-=y;
		}else{
			sum=sum+y-q;
			q=0;
		}
		if(q==0){
			sum++;
			q++;
		}
		q+=z;
	}
	for(int i=1;i<=m;i++){
		long long int t,tt;
		cin>>t>>tt;
	}
	cout<<sum;
}

上一题

© 2025 nowcoder.com