31545번 - 최소 스패닝 트리 다시 그리기 놀이 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 19 | 9 | 9 | 81.818% |
문제
하늘이는 최근 입대하였다. 하늘이의 선임은 하늘이가 사회에서 코딩하다 온 것을 알고, 하늘이에게 다음과 같이 ”최소 스패닝 트리 다시 그리기 놀이”를 알려 주었다.
- 먼저 선임이 후임에게 무향 연결 그래프 $G$를 준다. 이때, $G$를 구성하는 간선의 가중치는 모두 $10^6$이하의 양의 정수이다.
- 후임은 $G$에서 그릴 수 있는 서로 다른 최소 스패닝 트리 중 동일한 확률로 최소 스패닝 트리 $T$를 하나 고른다.
- 선임은 $1$부터 $10^6$까지 차례대로 각각 독립적으로, 정수 $x$를 $\frac{1}{x}$의 확률로 후임에게 말한다. 즉, $1$은 반드시 말하므로, 최소 $1$개 이상 $10^6$개 이하의 수를 말한다.
- 후임은 선임이 $x$를 말하면 $T$에서 가중치가 $x$인 간선을 모두 지운다. $T$에서 간선들이 지워진 상태를 $T^\prime$이라고 하자.
- 후임은 $T^\prime$에, 원래 그래프 $G$에 있는 간선을 $0$개 이상 추가하여 다시 $G$의 최소 스패닝 트리를 만든다.
하늘이는 이 놀이를 듣고, 새로 그릴 수 있는 최소 스패닝 트리의 개수가 몇 개인지 궁금해졌다. 선임이 후임에게 주는 그래프 $G$가 주어졌을 때, ”최소 스패닝 트리 다시 그리기 놀이”를 통해 그릴 수 있는 최소 스패닝 트리의 개수의 기댓값을 구해보자.
입력
첫 번째 줄에 $G$의 정점의 개수 $V$과 간선의 개수 $E$가 공백으로 구분되어 주어진다. $(2\le V\le 500;$ $V-1\le E\le\frac{V(V-1)}{2})$
두 번째 줄부터 $E$개의 줄에 걸쳐 $G$의 간선의 정보를 나타내는 정수 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어진다. 이는 $u_i$번 정점과 $v_i$번 정점을 연결하는 가중치 $w_i$의 간선이 존재한다는 의미이다. $(1\le u_i, v_i\le V;$ $u_i \ne v_i;$ $1\le w_i\le 10^6)$
주어지는 그래프는 연결 그래프이며, 임의의 두 정점 사이의 간선은 최대 한 개 존재함이 보장된다.
출력
$G$에 대해 “최소 스패닝 트리 다시 그리기 놀이”를 통해 그릴 수 있는 최소 스패닝 트리의 개수의 기댓값을 $10^9+7$로 나눈 나머지를 출력한다.
기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.
만약 정답의 분모가 $10^9+7$의 배수인 경우 기댓값 대신 -1을 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 23 | $E = V-1$ |
| 2 | 66 | $V\le 4$ |
| 3 | 65 | 모든 $w_i = 1;$ $E=\frac{V(V-1)}{2}$ |
| 4 | 49 | 모든 $w_i = 1$ |
| 5 | 95 | 모든 $w_i \le 2$ |
| 6 | 152 | 추가적인 제한 조건 없음 |
예제 입력 1
4 6 1 2 1 1 3 1 1 4 1 2 3 1 2 4 1 3 4 1
예제 출력 1
16
주어진 그래프는 아래 그림과 같다.
이 그래프의 최소 스패닝 트리는 다음 $16$가지로, $\frac{1}{16}$의 확률로 하나를 후임이 고른다.
어떤 그래프를 골라도, $T^\prime$은 반드시 아래와 같은 상태가 되고, 다시 $16$개의 최소 스패닝 트리를 모두 만들 수 있다.
예제 입력 2
5 5 5 1 1 2 4 2 4 5 2 1 2 1 4 3 1
예제 출력 2
500000005
주어진 그래프는 아래 그림과 같다.
이 그래프의 최소 스패닝 트리는 다음 $2$가지로, $\frac{1}{2}$의 확률로 하나를 후임이 고른다.
이후 가능한 조합은 다음과 같다. 기댓값은 $\frac{3}{2}$이다.
예제 입력 3
8 9 1 2 1 2 3 1 3 4 1 4 1 1 1 3 1 1 5 1 2 6 1 3 7 1 4 8 1
예제 출력 3
8
예제 입력 4
23 23 20 21 108108 23 1 309309 4 5 1000000 16 17 108108 21 22 1000000 19 20 124124 14 15 124124 7 8 108108 2 3 124124 3 4 309309 10 11 309309 22 23 108108 9 10 108108 13 14 1000000 15 16 309309 8 9 108108 1 2 1000000 5 6 1000000 12 13 108108 18 19 309309 17 18 1000000 6 7 309309 11 12 1000000
예제 출력 4
857142007
출처
University > 고려대학교 > MatKor Cup > 제4회 고려대학교 MatKor Cup: 2024 Winter/Spring M번
- 문제를 만든 사람: alex04, eoaud0108, kidw0124
- 문제를 번역한 사람: tikiliki0417
- 문제를 검수한 사람: devluyten, finimage, gs25, tlsdydaud1, utilforever, yijw0930
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호