oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

simplify Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

simplify.txt

Problem 2: Simplifying the Farm [Nathan Pinsker, 2011]

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.

Tags

USACO Gold Dec 2011, Graph Theory, Minimum Spanning Tree

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100121s16MBAverage

Judge Compile Command

g++-8 ans.cpp -o simplify -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.