SOLVE
LATER
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:
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
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\).