DMOPC '15 Contest 6 P4 - Line Graph

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type

The minimum spanning tree of a graph is defined as a tree which contains all the vertices, and does so using the smallest accumulative weight of edges.

You are given a graph in the shape of a line: it has N vertices and N-1 edges, where the i-th edge connects vertices i and i+1, using weight w_i. You are also given an integer K: there exists an arbitrary number of "network trampolines," indicating that a weightless edge connects the i-th vertex to the i+K-th vertex, given that both exist, for all values of i. You are also allowed to use the other existing edges as necessary.

All edges are undirected.

Find the minimum spanning tree of the graph by outputting the sum of the weights of all encompassed edges.

Input Specification

On the first line, there will be the integer N, followed by a space, followed by the integer K.

On the next line, there will be N-1 space-separated integers, the i-th being w_i, the weight of the edge connecting the i-th vertex with the i+1-th vertex. (It should be assumed that the vertices are numbered from 1 to N.)


For all subtasks:

1 \le K \le 100\,000

For all i from 1 to N-1, 0 \le w_i \le 1\,000.

Subtask 1 [35%]

2 \le N \le 12

Subtask 2 [20%]

2 \le N \le 1\,001

Subtask 3 [45%]

2 \le N \le 100\,000

Output Specification

Print a single integer, the combined weight of the graph's minimum spanning tree.

Sample Input 1

3 2
3 5

Sample Output 1


Explanation for Sample 1

There are three vertices in this graph. 1 and 2 are connected by an edge of weight 3, 2 and 3 by one of weight 5, and it can be deduced that, since K=2 and 3-1=2, 1 and 3 are connected by an edge of weight 0. The minimum spanning tree consists of the 0-weight edge and the 3-weight edge, which spans all the vertices.

Sample Input 2

5 2
5 6 7 8

Sample Output 2


Explanation for Sample 2

There are five edges: edges of weight 0 exist from 1 to 3, 3 to 5, and 2 to 4. Take all of these edges, along with the edge connecting 1 and 2, and the minimum spanning tree is complete.

Sample Input 3

5 3
5 6 7 8

Sample Output 3



  • 3
    Nils_Emmenegger  commented on June 14, 2021, 7:23 p.m.

    Once you've solved the problem, check out LNY's submission for an (IMO) pretty neat linear-time solution.