#P16348. [2026年山东第二轮集训]最优化问题

    ID: 15559 传统题 4000ms 1024MiB 尝试: 2 已通过: 1 难度: 7 上传者: 标签>CF2200图论数学贪心最短路动态规划算法基础排序

[2026年山东第二轮集训]最优化问题

题目描述

有 nn 种类型的男生和 2⋅n2 \cdot n 个女生。男生的类型用从 11 到 nn 的整数编号,而女生用从 11 到 2⋅n2 \cdot n 的整数编号。

第 ii 种类型的男生有 cic_i 个,这 cic_i 个男生中的每一个都喜欢编号为 aia_i 和 bib_i 的女生。

求一个最大的男生集合的大小,使得对于该集合中的任意两个男生,至少存在一个女生被他们两人都喜欢。

本题中,每个测试点包含多组输入数据。你需要对每组数据独立求解。

输入格式

第一行包含一个整数 TT (1≤T≤500)(1 \le T \le 500) —— 输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含一个整数 nn (1≤n≤107)(1 \le n \le 10^7)。

接下来的 nn 行,每行包含三个整数 aia_i, bib_i, cic_i $(1 \le a_i < b_i \le 2 \cdot n, 1 \le c_i \le 10^9)$ —— 对应类型男生的参数。

保证对于任意 1≤i<j≤n1 \le i < j \le n,满足 ai≠aja_i \ne a_j 或 bi≠bjb_i \ne b_j。

保证单个测试点中所有输入数据的 nn 之和不超过 10710^7。

输出格式

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

样例 1 输入

3
2
1 2 3
3 4 5
5
1 2 1
1 3 4
4 5 2
3 4 2
1 4 3
4
1 2 3
2 3 4
3 5 4
1 3 2

样例 1 输出

5
9
10

数据范围

令 S=∑nS=\sum n,则对于全部数据:1≤S≤1071 \le S \le 10^7,1≤ai<bi≤2⋅n,1≤ci≤1091 \le a_i < b_i \le 2 \cdot n, 1 \le c_i \le 10^9,对于任意 1≤i<j≤n1 \le i < j \le n,满足 ai≠aja_i \ne a_j 或 bi≠bjb_i \ne b_j。

  • 子任务 1(1010 分):n≤5n \le 5;
  • 子任务 2(1010 分):S≤7⋅105S\le 7\cdot 10^5,每个女生最多被两种类型的男生喜欢;
  • 子任务 3(2020 分):S≤3000S \le 3000;
  • 子任务 4(2020 分):S≤7⋅105S\le 7\cdot 10^5;
  • 子任务 5(4040 分):无额外限制。