分数: 1200 点
问题陈述
我们有 N 盒子编号 1 to N,和 M 球编号 1 to M。 目前,鲍尔 i 装在盒子里 A_i.
您可以执行以下操作:
- 选择一个包含两个或多个球的盒子,从该盒子中拿起其中一个球,然后将其放入另一个盒子中。
由于球很容易损坏,因此您无法移动球 i 超过 总共 C_i 次。 在此限制内,您可以执行任意次数的操作。
你的目标是拥有鲍尔 盒子里的 i 盒装 B_i 对于每个 i (1 \leq i \leq M)。 确定这个目标是否可以实现。 如果是,还需要找到实现它所需的最少操作数。
约束
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq A_i,B_i \leq N
- 1 \leq C_i \leq 10^5
- 在达到目标的情况下,每个盒子包含一个或多个球。 也就是说,对于每一个 i (1 \leq i \leq N),存在 j 这样 B_j=i.
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
输出
如果目标无法实现,则打印 -1;如果可以实现,请打印实现它所需的最少操作数。
示例输入 1
3 3 1 2 1 2 1 1 1 3 2
示例输出 1
3
我们可以通过三个操作来实现该目标,如下所示:
- 捡球 1 来自盒子 1 并将其放入盒子中 2.
- 捡球 2 来自盒子 2 并将其放入盒子中 1.
- 捡球 3 来自盒子 1 并将其放入盒子中 3.
示例输入 2
2 2 1 2 1 2 1 1
示例输出 2
-1
示例输入 3
5 5 1 2 1 2 1 1 1 3 2 4 5 1 5 4 1
示例输出 3
6
示例输入 4
1 1 1 1 1
示例输出 4
0