| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 54 | 44 | 42 | 80.769% |
윤이와 달구와 포닉스는 바닥에 고정된 고리에 $N$개의 풍선과 $M$개의 실을 이어서 UDPC를 상징하는 조형물을 만들고 있다. 실을 이용하면 풍선과 풍선, 또는 풍선과 고리를 연결할 수 있다. 풍선은 자신에게 연결된 실 중 어느 하나가 팽팽해질 때까지 위로 떠오른다. 실이 꼬이거나 풍선끼리 부딪히는 경우는 없다고 가정하며, 풍선의 크기는 무시한다.
완성된 조형물을 살펴보던 포닉스는 실이 너무 많이 연결된 것 같아서 필요하지 않은 실을 잘라내기로 했다. 실을 자르고 난 뒤에는 풍선의 높이가 변하거나 풍선이 멀리 날아가 버리면 안 된다. 포닉스는 더이상 잘라낼 수 있는 실이 없을 때까지 실을 자를 것이다.
달구는 남은 실의 길이의 합이 가장 크도록 실을 자르자고 제안했다. 하지만 어떻게 잘라야 좋을지 몰라서 윤이에게 물어보기로 했다. 윤이와 함께 실을 어떻게 자르면 좋을지 계산해 주자!
첫째 줄에 풍선의 개수 $N$과 실의 개수 $M$이 공백으로 구분되어 주어진다. $(1 \le N \le 100\,000; 1 \le M \le 300\,000)$
다음 $M$개의 줄에 실이 잇는 풍선 또는 고리의 번호 쌍 $u$, $v$와 실의 길이 $w$가 공백으로 구분되어 주어진다. $(0 \le u, v \le N; u \ne v; 1 \le w \le 10^9)$
풍선의 번호는 $1$ 이상 $N$ 이하의 정수이고, 고리의 번호는 $0$이다. 같은 번호 쌍이 여러 번 주어질 수 있다.
모든 풍선은 실을 통해 고리에 직접 또는 간접적으로 연결되어 있음이 보장된다. 즉, 처음부터 멀리 날아가 버리는 풍선은 없다.
잘라야 하는 실의 개수 $K$와 남은 실의 길이의 합 $L$을 공백으로 구분하여 출력한다.
2 3 0 1 3 1 2 5 0 2 10
1 8
4 4 0 1 20 1 2 30 2 3 40 2 4 50
0 140
3 7 0 1 3 0 1 10 0 2 2 2 1 1 1 3 7 3 2 8 3 0 11
4 13
University > UNIST-DGIST-POSTECH > 2026 UNIST-DGIST-POSTECH 연합 프로그래밍 경진대회 (2026 UDPC) > Senior Division E번