레이팅 미적용농부 존(Farmer John)은 동네 대학에서 야간 알고리즘 강의를 듣고 있는데, 방금 최소 신장 트리에 대해 배웠다. 그런데 농부 존은 자기 농장의 설계가 생각만큼 효율적이지 않다는 것을 깨닫고, 농장의 구조를 단순화하고 싶어졌다.
농장은 현재 그래프처럼 배치되어 있는데, 정점은 목초지를, 간선은 목초지 사이의 길을 나타내며 각 길에는 길이가 있다. 농부 존은 각 길이 값마다 그 길이를 가지는 길이 농장에 최대 세 개뿐이라는 점에 주목했다. FJ는 농장의 길 일부를 없애서 농장이 트리가 되게, 즉 임의의 두 목초지 사이에 유일한 경로가 존재하게 만들고 싶다. 게다가 농부 존은 이것이 최소 신장 트리, 즉 간선 길이의 합이 가능한 한 작은 트리이기를 원한다.
농장 그래프에서 얻은 최소 신장 트리의 간선 길이 합뿐만 아니라, 만들 수 있는 서로 다른 최소 신장 트리의 개수까지 계산하는 것을 농부 존에게 도와주자.
첫째 줄: 농장 그래프의 정점 수와 간선 수를 나타내는 두 정수 N과 M (1 <= N <= 40,000; 1 <= M <= 100,000). 정점은 1..N으로 번호가 붙어 있다.
둘째 줄부터 M+1번째 줄까지: 정점 a_i에서 b_i로 가는 길이 n_i의 간선을 나타내는 세 정수 a_i, b_i, n_i (1 <= a_i, b_i <= N; 1 <= n_i <= 1,000,000). 어떤 간선 길이 n_i도 세 번을 초과하여 나타나지 않는다.
최소 신장 트리의 길이와 최소 신장 트리의 개수(1,000,000,007로 나눈 나머지)를 나타내는 두 정수.
simplify.in · 출력을 쓸 파일 simplify.out4 5
1 2 1
3 4 1
1 3 2
1 4 2
2 3 24 3Output details: Picking both edges with length 1 and any edge with length 2 yields a minimum spanning tree of length 4.
riseoj 작성
출처 올림피아드 > USACO > 2011-2012 > December > Gold