P12544 [UOI 2025] Boys and Girls

有 $n$ 种类型的男孩和 $2 \cdot n$ 个女孩。男孩的类型用从 $1$ 到 $n$ 的整数编号，而女孩用从 $1$ 到 $2 \cdot n$ 的整数编号。 第 $i$ 种类型的男孩有 $c_i$ 个，这 $c_i$ 个男孩中的每一个都喜欢编号为 $a_i$ 和 $b_i$ 的女孩。 求一个最大的男孩集合的大小，使得对于该集合中的任意两个男孩，至少存在一个女孩被他们两人都喜欢。 本题中，每个测试点包含多组输入数据。你需要对每组数据独立求解。

第一行包含一个整数 $T$ $(1 \le T \le 500)$ —— 输入数据的组数。接下来是各组数据的描述。 每组数据的第一行包含一个整数 $n$ $(1 \le n \le 7 \cdot 10^5)$。 接下来的 $n$ 行，每行包含三个整数 $a_i$, $b_i$, $c_i$ $(1 \le a_i < b_i \le 2 \cdot n, 1 \le c_i \le 10^9)$ —— 对应类型男孩的参数。 保证对于任意 $1 \le i < j \le n$，满足 $a_i \ne a_j$ 或 $b_i \ne b_j$。 保证单个测试点中所有输入数据的 $n$ 之和不超过 $7 \cdot 10^5$。

对于每组输入数据，输出一行一个整数 —— 满足条件的最大男孩集合的大小。

设 $S$ 为单个测试点中所有输入数据的 $n$ 之和，$K$ 为单个测试点中所有 $c_i$ 之和。 - （$5$ 分）：$n \le 5$； - （$11$ 分）：$S \le 100$； - （$7$ 分）：每个女孩最多被两种类型的男孩喜欢； - （$10$ 分）：$S \le 3000$； - （$23$ 分）：$S \le 3 \cdot 10^5$； - （$19$ 分）：$K \le 10^7$； - （$25$ 分）：无额外限制。 对样例第二组输入数据的解释： - 如果我们选择类型为 2、4 和 5 的男孩，我们可以得到答案 9。也就是说，被选中的男孩喜欢的女孩对 $(a_i, b_i)$ 为 $(1, 3)$、$(3, 4)$ 和 $(1, 4)$。 - 很容易看出，对于这个集合中的任意一对男孩，都存在至少一个他们共同喜欢的女孩。