Graph Reduce

4.7

3 votes
Graph, Approximate, Very-Easy, Shortest path problem
Problem

Given an undirected graph with N vertices and M edges, you need to delete C edges, and keep the graph connected. Then we can calculate N(N1)2 shortest distances of pairs of vertices.
You goal is to maximize the K th maximum distance.

Input Format

First line contains four integers, N,M,C,K.

Each of the next M lines contains two integers u,v,w, represents an edge between u and v which weighted w. It's guaranteed there is no multiple edges or self loops.

Output Format

C lines, each line contains two integers, represents one deleted edge.

Scoring

If your output is illegal, score is 0, otherwise it will be the Kth maxinum distancesum of weight of edges in the original graph.

Test generation

N=512

M of i th(1i50) input file is i2606+516

C is random selected in range [1000,MN]

K is random selected in range [1,N(N1)2]

The graph generation is, first generate a random tree, then add MN+1 random edges on it.

w is random selected in range [1,109].

Test data will be regenerated with different seeds after the contest.

Time Limit: 3
Memory Limit: 256
Source Limit:
Explanation

Score=361.2247448713915892

Edge (1,2) can also reach this answer.

Editor Image

?