A16159 | The Third Letter
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
In order to win his toughest battle, Mircea came up with a great strategy for his army. He has $n$ soldiers and decided to arrange them in a certain way in camps. Each soldier has to belong to exactly one camp, and there is one camp at each integer point on the $x$ -axis (at points $\cdots, -2, -1, 0, 1, 2, \cdots$ ).
The strategy consists of $m$ conditions. Condition $i$ tells that soldier $a_i$ should belong to a camp that is situated $d_i$ meters in front of the camp that person $b_i$ belongs to. (If $d_i < 0$ , then $a_i$ 's camp should be $-d_i$ meters behind $b_i$ 's camp.)
Now, Mircea wonders if there exists a partition of soldiers that respects the condition and he asks for your help! Answer "YES" if there is a partition of the $n$ soldiers that satisfies all of the $m$ conditions and "NO" otherwise.
Note that two different soldiers may be placed in the same camp.
The strategy consists of $m$ conditions. Condition $i$ tells that soldier $a_i$ should belong to a camp that is situated $d_i$ meters in front of the camp that person $b_i$ belongs to. (If $d_i < 0$ , then $a_i$ 's camp should be $-d_i$ meters behind $b_i$ 's camp.)
Now, Mircea wonders if there exists a partition of soldiers that respects the condition and he asks for your help! Answer "YES" if there is a partition of the $n$ soldiers that satisfies all of the $m$ conditions and "NO" otherwise.
Note that two different soldiers may be placed in the same camp.
输入格式
The first line contains a single integer $t$ ( $1 \leq t \leq 100$ ) — the number of test cases.
The first line of each test case contains two positive integers $n$ and $m$ ( $2 \leq n \leq 2 \cdot 10^5$ ; $1 \leq m \leq n$ ) — the number of soldiers, and the number of conditions respectively.
Then $m$ lines follow, each of them containing $3$ integers: $a_i$ , $b_i$ , $d_i$ ( $a_i \neq b_i$ ; $1 \leq a_i, b_i \leq n$ ; $-10^9 \leq d_i \leq 10^9$ ) — denoting the conditions explained in the statement. Note that if $d_i$ is positive, $a_i$ should be $d_i$ meters in front of $b_i$ and if it is negative, $a_i$ should be $-d_i$ meters behind $b_i$ .
Note that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$ .
The first line of each test case contains two positive integers $n$ and $m$ ( $2 \leq n \leq 2 \cdot 10^5$ ; $1 \leq m \leq n$ ) — the number of soldiers, and the number of conditions respectively.
Then $m$ lines follow, each of them containing $3$ integers: $a_i$ , $b_i$ , $d_i$ ( $a_i \neq b_i$ ; $1 \leq a_i, b_i \leq n$ ; $-10^9 \leq d_i \leq 10^9$ ) — denoting the conditions explained in the statement. Note that if $d_i$ is positive, $a_i$ should be $d_i$ meters in front of $b_i$ and if it is negative, $a_i$ should be $-d_i$ meters behind $b_i$ .
Note that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$ .
输出格式
For each test case, output "YES" if there is an arrangement of the $n$ soldiers that satisfies all of the $m$ conditions and "NO" otherwise.
输入输出样例
输入 #1
4 5 3 1 2 2 2 3 4 4 2 -6 6 5 1 2 2 2 3 4 4 2 -6 5 4 4 3 5 100 2 2 1 2 5 1 2 4 4 1 1 2 3
输出 #1
YES NO NO YES
For the first test case, we can partition the soldiers into camps in the following way: soldier:
- Soldier $1$ in the camp with the coordinate $x = 3$ .
- Soldier $2$ in the camp with the coordinate $x = 5$ .
- Soldier $3$ in the camp with the coordinate $x = 9$ .
- Soldier $4$ in the camp with the coordinate $x = 11$ .
For the second test case, there is no partition that can satisfy all the constraints at the same time.
For the third test case, there is no partition that satisfies all the constraints since we get contradictory information about the same pair.
For the fourth test case, in order to satisfy the only condition, a possible partition is:
- Soldier $1$ in the camp with the coordinate $x = 10$ .
- Soldier $2$ in the camp with the coordinate $x = 13$ .
- Soldier $3$ in the camp with the coordinate $x = -2023$ .
- Soldier $4$ in the camp with the coordinate $x = -2023$ .
- Soldier $1$ in the camp with the coordinate $x = 3$ .
- Soldier $2$ in the camp with the coordinate $x = 5$ .
- Soldier $3$ in the camp with the coordinate $x = 9$ .
- Soldier $4$ in the camp with the coordinate $x = 11$ .
For the second test case, there is no partition that can satisfy all the constraints at the same time.
For the third test case, there is no partition that satisfies all the constraints since we get contradictory information about the same pair.
For the fourth test case, in order to satisfy the only condition, a possible partition is:
- Soldier $1$ in the camp with the coordinate $x = 10$ .
- Soldier $2$ in the camp with the coordinate $x = 13$ .
- Soldier $3$ in the camp with the coordinate $x = -2023$ .
- Soldier $4$ in the camp with the coordinate $x = -2023$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted