| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 130 | 33 | 26 | 42.623% |
우진이와 연두는 별자리를 좋아한다. 둘의 취향은 약간 다른데, 우진이는 직선을 좋아하고 연두는 원을 좋아한다. 준원이는 둘을 위해 별자리가 그려진 그림을 선물하려고 한다.
준원이는 먼저 종이 위에 $N$개의 별을 그렸다. 그 뒤 두 별을 잇는 $M$개의 간선을 그렸다. 준원이는 이제 마지막 작업으로 두께가 $K$ 이상인 모든 간선만을 강조할 예정이다. $K$는 간선의 두께 중에서 고른다.
준원이는 우진이와 연두 모두와 친하기 때문에 강조된 간선으로만 이루어진 그림에서 직선과 원의 개수 차이를 최소로 하려고 한다.
직선의 개수와 원의 개수 차이를 최소로 하는 $K$가 여러 가지라면 준원이는 그중 가장 작은 값을 택할 것이다. 많은 간선이 강조된 그림일수록 아름답기 때문이다.
준원이가 택할 $K$의 값과 그때 직선과 원의 개수 차이를 구해주자.
첫 번째 줄에 별의 개수 $N$, 간선의 개수 $M$이 공백으로 구분되어 주어진다.
이후 $M$개의 줄에 걸쳐 간선들의 정보가 주어진다.
각 줄에는 세 개의 정수 $X$, $Y$, $W$가 공백으로 구분되어 주어지며, 이는 $X$번 별과 $Y$번 별을 연결하는 두께 $W$의 간선을 나타낸다.
준원이가 택할 $K$의 값과 그때 직선과 원의 개수 차이를 공백으로 구분하여 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 30 | 모든 간선의 두께는 $1$이다. |
| 2 | 70 | 추가 제약 조건이 없음. |
5 4 1 2 1 2 3 1 4 5 3 3 1 2
1 0
6 6 1 2 3 2 3 3 3 1 3 4 5 2 5 6 2 6 4 2
3 1
4 5 4 3 2 1 4 5 1 2 3 3 2 4 3 1 1
1 0
2 1 1 2 1
1 1