#P8896. 「DPOI-1」道路规划
「DPOI-1」道路规划
题目背景
不可以,总司令。
题目描述
战场上有 个据点,从 编号。每两个据点之间都有一条双向道路。
一天,总司令来战区巡视,走着走着迷路了,于是愤怒地下达命令,让你把每一条双向道路变成单向的,使得这些道路不包含环(否则总司令会迷路)。但由于每个据点的规模互不相同,总司令从第 个据点出发沿着单向道路能直接到达的据点数量需要在 之间。换言之,第 个点的出度需要在 之间。你需要告诉总司令有没有可能满足他的需求。
输入格式
本题有多组测试数据。
第一行,一个整数 ,表示数据组数。
对于每组数据:
第一行,一个整数 ,表示据点数量;
第二行, 个整数 ;
第三行, 个整数 。
输出格式
对于每组数据:
一行,一个字符串。若可以满足总司令的需求,一行 YES
;否则,一行 NO
。
2
5
0 1 4 0 0
3 4 4 1 3
3
1 2 2
2 2 2
YES
NO
见下发文件 road2.in
见下发文件 road2.out
提示
样例 #1 解释
下面是第 组数据中一种可行的方案:
样例 #2 解释
该样例满足测试点 的限制。
数据范围
本题测试点分数不等分。
测试点编号 | 特殊条件 | 每个测试点分数 | |
---|---|---|---|
无 | |||
所有 或所有 | |||
或 | |||
无 |
对于 的数据,,,。