시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
4.2 초 (추가 시간 없음) | 512 MB (추가 메모리 없음) | 108 | 22 | 17 | 18.085% |
왼쪽 정점, 오른쪽 정점의 개수가 $N$개, 간선의 개수가 $M$개, 각 정점의 degree가 최대 2인 이분 그래프가 주어진다. 왼쪽 정점과 오른쪽 정점에는 각각 $1$부터 $N$까지 번호가 매겨져 있고, 서로 다른 두 정점 사이에는 최대 한 개의 간선이 존재한다.
Matching은 간선의 양 끝점이 중복되지 않게 선택한 간선의 집합을 의미한다. 크기가 $1$, $2$, ..., $N$인 Matching의 최소 비용을 각각 구해보자.
첫 번째 줄에 정점의 개수 $N$, 간선의 개수 $M$이 주어진다. ($1 \le N \le 500\,000$, $0 \le M \le 2N$)
다음 $M$개의 줄에 걸쳐서 간선의 정보를 나타내는 $(x,y,c)$가 순차적으로 주어진다. $x$는 왼쪽 정점의 번호, $y$는 오른쪽 정점의 번호, $c$는 해당 간선의 비용을 의미한다. ($1 \le x,y \le N$, $1 \le c \le 1\,000\,000\,000$)
$N$개의 줄에 걸쳐서 $i$번째 줄에 크기가 $i$인 Matching의 최소 비용을 출력하자. 만약에 이러한 Matching이 없는 경우 -1
을 출력한다.
3 3 1 1 1 2 2 2 3 3 3
1 3 6
1 0
-1
University > 연세대학교 > 2021 연세대학교 프로그래밍 경진대회 M번