在一座科技先进的城市中,有 nn 个能源核心,编号从 11 到 nn,每个核心都蕴含独特的能量。为了优化城市运行,工程师们设计了 mm 个能源利用项目,编号从 11 到 mm。第 ii 个项目可以使用能源核心 aiai 或者 bibi 中的其中一个来激活,并且激活该项目可以获得价值 wiwi。然而,每个能源核心的能量有限,最多只能支持一个项目。你的任务是选择一些项目,并为每个项目指定使用的能源核心,使得总价值最大,同时保证每个核心最多被一个项目使用。请你求出这个最大值。
为了防止输入过大带来的常数问题,C++ 选手请尽量使用关闭流同步的 std::cin 和 std::cout 实现输入输出,否则可能出现因读入输出问题导致的 TLE 等。
int main(){ std::ios::sync_with_stdio(0); std::cin.tie(0); // your code return 0; }
第一行一个整数 TT (1≤T≤106)(1≤T≤106),表示测试数据组数。
每组数据的第一行包含两个整数 nn 和 mm (1≤n,m≤2×105)(1≤n,m≤2×105),分别表示资源点数量和项目数量。
接下来 mm 行,每行包含三个整数 ai,bi,wiai,bi,wi (1≤ai,bi≤n,ai≠bi,1≤wi≤109)(1≤ai,bi≤n,ai=bi,1≤wi≤109),分别表示项目 ii 关联的两个能源核心和项目 ii 的价值。
保证所有测试数据的 nn 之和和 mm 之和均不超过 2×1062×106。
3
3 7
2 1 6
1 3 7
3 1 2
1 3 2
3 2 2
1 3 7
3 2 1
4 4
3 2 10
4 3 6
1 2 1
3 4 1
5 8
5 2 8
4 3 6
5 1 10
2 5 1
2 1 4
4 5 4
5 1 1
2 5 1
20
18
32