HKRUSKAL - Simplifying the Farm

no tags 

Farmer John has been taking an evening algorithms course at his local

university, and he has just learned about minimum spanning trees. However,

Farmer John now realizes that the design of his farm is not as efficient as

it could be, and he wants to simplify the layout of his farm.

 

The farm is currently arranged like a graph, with vertices representing

fields and edges representing pathways between these fields, each having an

associated length. Farmer John notes that for each distinct length,

at most three pathways on his farm share this length. FJ would like to

remove some of the pathways on his farm so that it becomes a tree -- that

is, so that there is one unique route between any pair of fields. Moreover,

Farmer John would like this to be a minimum spanning tree -- a tree having

the smallest possible sum of edge lengths.

 

Help Farmer John compute not only the sum of edge lengths in a minimum

spanning tree derived from his farm graph, but also the number of different

possible minimum spanning trees he can create.

 

PROBLEM NAME: simplify

 

INPUT FORMAT:

 

* Line 1: Two integers N and M (1 <= N <= 40,000; 1 <= M <= 100,000),

representing the number of vertices and edges in the farm

graph, respectively. Vertices are numbered as 1..N.

 

* Lines 2..M+1: Three integers a_i, b_i and n_i (1 <= a_i, b_i <= N; 1

<= n_i <= 1,000,000) representing an edge from vertex a_i to

b_i with length n_i. No edge length n_i will occur more than

three times.

 

SAMPLE INPUT (file simplify.in):

 

4 5

1 2 1

3 4 1

1 3 2

1 4 2

2 3 2

 

OUTPUT FORMAT:

 

* Line 1: Two integers representing the length of the minimal spanning

tree and the number of minimal spanning trees (mod

1,000,000,007).

 

SAMPLE OUTPUT (file simplify.out):

 

4 3

 

OUTPUT DETAILS:

 

Picking both edges with length 1 and any edge with length 2 yields a minimum

spanning tree of length 4.



Added by:DVH
Date:2013-12-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:USACO 2011 December Contest, Gold Division