페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#2622

[고등부] 2025 KOI 2차대회 대비 모의고사 (2회차)

네트워크 구축 3초 1024MB

문제

정부는 N개의 집이 서로 연락을 할 수 있도록 통신선을 구축하려고 한다.

모든 집은 1 이상 N 이하의 서로 다른 정수 번호가 할당되어 있다.

정부는 KOI 텔레콤과 IOI 네트워크 두 개의 통신사에 적절하게 투자하여 통신선을 구축할 계획이다.

정부는 각 회사에 통신망 구축 계획을 요청했고,
이에 따라 두 회사는 통신선을 구축하는 두 집의 번호와 통신선 구축 난이도의 리스트를 제출했다.

정부는 두 회사에 각각 0 이상의 돈을 투자할 수 있다.

투자가 끝나면 각 회사는 통신선을 구축하는데, 정부에게 l만큼 투자받은 회사는
자신의 구축 계획에 있는 통신선 중 구축 난이도가 l 이하인 모든 통신선을 구축한다.

두 집이 서로 통신하기 위해서는 같은 회사의 전화선으로 직·간접적으로 연결되어 있어야 한다.

정부는 서로 통신할 수 있는 두 집의 쌍이 K쌍 이상이 되게 하려고 한다.

통신망 구축 계획이 주어지면 최소 비용의 투자로 많은 집들이 통신할 수 있도록 투자 계획을 계산하여라.


입력

첫 번째 줄에는 집의 수 N, KOI 텔레콤의 통신선 수 A, IOI 네트워크의 통신선 수 B, 요구조건 K가 공백을 사이에 두고 주어진다.

다음 A개의 줄에는 KOI 텔레콤의 통신선 정보를 나타내는 세 개의 정수 u, v, l이 공백을 사이에 두고 주어진다.

이는 KOI 텔레콤이 u번 집과 v번 집(1 \le u, v \le N)을 연결하는 통신선을 구축할 수 있고 통신선 구축 난이도가 l (1 \le l \le 10^9)이라는 의미이다.

다음 B개의 줄에는 IOI 네트워크의 통신선 정보가 앞선 A개의 줄과 동일한 형식으로 주어진다.


출력

최소 K쌍의 집끼리 통신하기 위해서 정부가 투자해야 하는 최소 비용을 출력한다.

만약 정부가 어떻게 투자하더라도 K쌍 이상의 집이 통신할 수 없다면 −1을 출력한다.


부분문제

번호 점수 조건
#124점

 1 \le N \le 2\,000, 0 \le A, B \le 200\,000, 0 \le K \le \frac{N(N - 1)}{2} 

#220점

 1 \le N \le 200\,000, 0 \le A, B \le 200\,000, 0 \le K \le \frac{N(N - 1)}{2} 

KOI 텔레콤이 구축하는 모든 통신선은 홀수 번호 집 두 개를 연결하며, IOI 네트워크가 구축하는 모든 통신선은 짝수 번호 집 두 개를 연결한다.

#324점

 1 \le N \le 200\,000, 0 \le A \le 10; 0 \le B \le 200\,000, 0 \le K \le \frac{N(N - 1)}{2}

#432점

 1 \le N \le 200\,000, 0 \le A, B \le 200\,000, 0 \le K \le \frac{N(N - 1)}{2}


예제 

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
33

각 회사별로 6가구가 전화선으로 연결된 방식을 보여주는 그림을 살펴보세요.

(참고로, 이 다이어그램은 아직 제공되지 않았습니다.)

정부가 KOI 텔레콤에 3만큼 투자하고 IOI 네트워크에 30만큼 투자하면, (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)는 KOI 텔레콤의 회선을 통해 통신할 수 있고, (1, 5), (2, 6), (3, 6), (2, 3)는 IOI 네트워크의 회선을 통해 통신할 수 있다. 33보다 적은 돈을 투자한다면 9쌍 이상의 집끼리 통신할 수 있게 하는 것이 불가능하다.

로그인해야 코드를 작성할 수 있어요.