[AdditionalFile5275.zip](file://AdditionalFile5275.zip?type=additional_file)

#5275. 「UOI 2019 Stage 4 Day1」科扎克·武斯与最佳国家

标签: 传统 | 时间限制: 2000 ms | 内存限制: 512 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 14 及以上）

请在提交源代码前添加 #include "grader.h"。

题目描述

题目译自 Ukrainian Olympiads in Informatics 2019 Stage 4 Day1 T4. Козак Вус і найкраща країна

科扎克·武斯终于找到了他梦想中的国家。这个国家有 $n$ 座城市，城市之间目前没有任何道路连接。当然，武斯想要改变这种情况，因此他设计了 $m$ 条不同的双向道路可以修建。每条道路连接两座不同的城市。但问题出现了：每座城市 $i$ 只能为修建道路提供 $c_i$ 个硬币，而每条道路 $j$ 的修建成本为 $w_j$ 个硬币。因此，武斯决定只修建部分道路，使得所有城市成为邻居即可。城市被称为邻居，如果可以通过国家内的道路从一座城市到达另一座城市。

在规划工作时，科扎克·武斯意识到一件事：当他修建一条新道路时，城市会合并成邻居群体。为了修建第 $j$ 条道路，连接的两座城市（或它们的邻居群体）必须总共拥有至少 $w_j$ 个硬币（因为需要先支付道路费用，然后才能修建）。修建道路后，城市的预算会合并，道路的成本将从新的公共资金中扣除。

对于每座城市 $i$，你知道 $c_i$，即城市 $i$ 能提供的硬币数量。对于每条道路 $m$，你知道 $v_i, u_i, w_i$，表示道路 $i$ 连接城市 $v_i$ 和 $u_i$，修建成本为 $w_i$ 个硬币。请判断是否可以选择一定数量的道路并按特定顺序修建，使得所有城市成为邻居。如果可以，请找出修建道路的序列。

交互方式

为了展示需要修建的道路，使用以下函数：

void add(integer i)

• 该函数修建编号为 $i$ $(1 \leq i \leq m)$ 的道路。

你需要实现以下函数：

boolean solve(integer n, integer m, integer g, array of integers c, array of integers v, array of integers u, array of integers w)

• $n$ —— 国家中的城市数量；
• $m$ —— 可以修建的道路数量；
• $g$ —— 子任务编号；
• $c_i$（数组 $c$ 的长度为 $n$）—— 第 $i$ 个城市的初始硬币数量；
• $v_i$ 和 $u_i$（数组 $v$ 和 $u$ 的长度均为 $m$）—— 第 $i$ 条道路连接的顶点编号；
• $w_i$（数组 $w$ 的长度为 $m$）—— 修建第 $i$ 条道路所需的硬币数量；
• 该函数应返回 $\texttt{true}$（如果可以正确选择道路序列）或 $\texttt{false}$（如果不可以）。

如果函数返回 $\texttt{true}$，则在返回之前，必须按修建顺序调用 $\texttt{add}$ 函数，添加所有修建的道路。

输入格式

第一行包含三个整数 $n, m, g$ $(1 \leq n \leq 10^{6}, 0 \leq m \leq 10^{6}, 0 \leq g \leq 7)$，分别表示城市数量、道路数量和子任务编号。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$ $(1 \leq c_i \leq 10^{6})$，表示第 $i$ 个城市的初始硬币数量。

接下来的 $m$ 行，每行包含三个整数 $v_i, u_i, w_i$ $(1 \leq v_i, u_i \leq n, 1 \leq w_i \leq 10^{6})$，分别表示第 $i$ 条道路连接的城市编号和修建成本。

输出格式

如果函数返回 $\texttt{false}$，则第一行输出一个数字 $-1$。

否则，第一行输出一个数字 $q$，表示修建的道路数量。接下来的 $q$ 行，每行输出一个数字 $x$，表示修建的道路编号。

样例 1

输入

4 5 0
2 5 2 4
1 2 7
3 4 4
1 4 5
4 2 3
3 2 4

输出

3
4
2
3

在第一个样例中，国家有 $4$ 座城市，科扎克·武斯的计划包含 $5$ 条道路。首先修建编号为 $4$ 的道路：城市 $2$ 和 $4$ 合并为一个群体，总预算中支付了 $3$ 个硬币。该群体的预算剩余 $6$ 个硬币。修建编号为 $2$ 的道路后，预算变为 $4$ 个硬币，因为城市 $3$ 加入带来 $2$ 个硬币，同时支付了 $4$ 个硬币修建道路。修建第 $3$ 条道路后，所有城市成为邻居，预算足够支付 $5$ 个硬币的道路费用。

样例 2

输入

3 3 0
6 2 5
2 3 9
2 1 5
1 3 10

输出

-1

在第二个样例中，无法选择道路及其修建顺序，使得所有城市成为邻居并支付所有道路的费用。

数据范围与提示

详细子任务附加限制及分值如下表所示：