#P10545. [2021年联测]碳

    ID: 9662 传统题 3000ms 888MiB 尝试: 4 已通过: 2 难度: 9 上传者: 标签>数据结构贪心图论CF2600并查集排序数学构造

[2021年联测]碳

碳(c)

题目描述

很久很久以前,有一个神秘的边带权无向图 GG,共包含nn个点和a+ba+b 条边,其中有aa 条边是蓝边,还有bb 条边是红边。 你需要选择两个非负整数x,yx , y,使得只保留边权≤x\leq x 的蓝边和边权 ≤y\leq y 的红边时,同色 连通的点对至少有kk 对。 求x+yx+y 的最小值,或报告无解。

一对点 (u,v)( u , v ) 是同色 连通的,当且仅当存在一条u→vu \to v的路径上所有边颜色相同,点对是无序的,并且 (u,u)( u , u ) 不算在 同色 连通点对之内。

输入格式

第一行:四个整数n,a,b,kn , a , b , k。

接下来aa 行:每行三个整数u,v,wu , v , w,描述一条u,vu , v 之间边权为 ww 的蓝边。

接下来 bb 行:每行三个整数u,v,wu , v , w,描述一条u,vu , v 之间边权为ww 的红边。

输出格式

输出一行一个整数,表示答案,如果无解则输出 -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 解释

令x=3,y=30x=3 , y=30,则点对$( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 )$ 可以通过蓝边连通,点对 (1,5),(2,3),(2,6),(3,6)( 1 , 5 ) , ( 2 , 3 ) , ( 2 , 6 ) , ( 3 , 6 ) 可以通过红边连通,并起来共有99 对同色 连通点对,这是所有符合题意的方案中x+yx+y 最小的一种。

样例 2 输入

2333 0 0 1

样例 2 输出

-1

样例 2 解释

没有任何边,自然不可能有同色 连通点对,所以无解。

数据范围

1≤n≤2×1051\le n\le2\times10^5,0≤a,b≤2×1050\le a,b\le2\times10^5,0≤k≤n(n−1)/20\le k\le n(n-1)/2,1≤u,v≤n1\le u,v\le n,1≤w≤1091\le w\le10^9。

子任务 分值 附加限制
1 20 n≤2000n\le2000
2 蓝边的两个端点都是奇数,红边的两个端点都是偶数
3 a≤10a\le10
4 40 无