시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 116 | 21 | 16 | 25.000% |
가중치가 있고, 연결되어있는 멀티 그래프 (connected weighted multigraph)가 주어졌을 때, 최소 스패닝 트리의 수를 구하는 프로그램을 작성하시오.
멀티 그래프는 루프(자기 자신으로 향하는 간선)이 있을 수 있고, 두 정점 사이에 간선이 여러 개 있을 수도 있다.
입력으로 주어지는 그래프에서 가중치가 같은 간선은 최대 4번 등장한다.
첫째 줄에 정점의 수 N과 간선의 수 M이 주어진다. (1 ≤ N ≤ 5×104, 1 ≤ M ≤ 105) 정점은 1번부터 N번까지 번호가 매겨져 있다. 다음 M개 줄에는 세 정수 a, b, w가 주어지며, 공백으로 구분되어져 있다. (1 ≤ a, b ≤ N, 1 ≤ w ≤ 230) 이 뜻은 a와 b를 연결하는 간선의 가중치가 w라는 뜻이다.
첫째 줄에 최소 스패닝 트리의 개수를 1000003로 나눈 나머지를 출력한다.
3 5 1 2 6 1 2 6 2 3 6 3 1 6 3 3 8
5
University > The MIT Programming Contest > 2008-09 > MIT Programming Contest Team Contest 1 2008 8번