All Tracks Algorithms Graphs Minimum Spanning Tree Problem

Worse MST
Tag(s):

Algorithms, Hard, Minimum spanning tree

Problem
Editorial
Analytics

For a given graph G with N vertices and M edges, where \(w_i\) denotes the weight of the i-th edge, the goal is to remove at most K edges from G producing a new graph G, in such a way that G is connected and the weight of minimum spanning tree of G is maximized.

Input format

In the first line, there are three space separated integer N, M and K, denoting respectively the number of vertices, the number edges, and the maximum allowed number of edges to be removed from the graph. After that, M lines follow. In the i-th of them there are three space-separated integers \(u_i\), \(v_i\), \(w_i\) denoting that the i-th edge in the graph connects vertices \(u_i\) and \(v_i\), and it has weight \(w_i\).

Output format

In the first line, print a single integer X, denoting the number of edges in your answer. In the second line, print X space-separated integers denoting the indices of the edges remaining in the graph. Just for clarification, the first edge given in the input has the index 1 and the last one has the index M.

Constraints

\(N = 5000\)
\(5 \cdot 10^4 \leq M \leq 10^5\)
\(100 \leq K \leq 5000\)
\(1 \leq w_i \leq 10^6\)
\(1 \leq u_i, v_i \leq N\)
the input graph is connected

Scoring

The answer is considered incorrect if:

  • The set of edges denoted by indices in the output is not a subset of edges given in the input.
  • The same edge appears multiple times in the output.
  • More than K edges were removed.
  • The resulting graph after removing the edges is not connected.

Otherwise, for a single test file its absolute score is:

\(\frac{MST(G')}{MST(G}\)

where \(MST(G)\) is the weight of minimum spanning tree of G.

The total absolute score of a submission is the sum of absolute scores across all test files. In this problem, scoring is set to relative, which means that the final score for a problem is your absolute score divided by the score of the best solution submitted by any participant. The objective is to maximize the total absolute score.

After the contest, new test files will be generated with the same method described below, and all submissions will be rejudged on these new test files.

Test generation

  • M is generated uniformly at random from range \([5 \cdot 10^4, 10^5]\)
  • K is generated uniformly at random from one of ranges: \([100,500]\), \([1000, 5000]\), and all these ranges are used equal number of times among test files
  • G is generated using this graph generation method
  • \(w_i\) for each i is generated uniformly at random from a range \([1, 10^6]\) and independently of other weights.
SAMPLE INPUT
4 4 2
1 2 2
1 3 2
1 4 2
2 3 1
SAMPLE OUTPUT
3
1 2 3
Explanation

In the sample output, the first 3 edges of the original graph remains, resulting in the weight of MST equal to 6. Since, the weight of MST of the original graph is 5, then the result for this output is \(1.2\).

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

April Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?