#P10545. [2021年联测]碳
[2021年联测]碳
碳(c)
题目描述
很久很久以前,有一个神秘的边带权无向图 ,共包含个点和 条边,其中有 条边是蓝边,还有 条边是红边。 你需要选择两个非负整数,使得只保留边权 的蓝边和边权 的红边时,同色 连通的点对至少有 对。 求 的最小值,或报告无解。
一对点 是同色 连通的,当且仅当存在一条的路径上所有边颜色相同,点对是无序的,并且 不算在 同色 连通点对之内。
输入格式
第一行:四个整数。
接下来 行:每行三个整数,描述一条 之间边权为 的蓝边。
接下来 行:每行三个整数,描述一条 之间边权为 的红边。
输出格式
输出一行一个整数,表示答案,如果无解则输出 -1。
样例 1 输入
6 4 4 9
1 2 1
2 3 2
1 4 3
3 4 4
5 6 40
1 5 30
2 6 20
3 6 10
样例 1 输出
33
样例 1 解释
令,则点对$( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 )$ 可以通过蓝边连通,点对 可以通过红边连通,并起来共有 对同色 连通点对,这是所有符合题意的方案中 最小的一种。
样例 2 输入
2333 0 0 1
样例 2 输出
-1
样例 2 解释
没有任何边,自然不可能有同色 连通点对,所以无解。
数据范围
,,,,。
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 1 | 20 | |
| 2 | 蓝边的两个端点都是奇数,红边的两个端点都是偶数 | |
| 3 | ||
| 4 | 40 | 无 |