Microsoft OA

You are given a network of data centers represented as nodes connected by bidirectional links (edges). Each link has a latency (weight).

You can remove some links to divide the network into at most k regions (connected components).

Your goal is to remove links such that the maximum latency (largest edge weight) within any region is as small as possible.

Example

Input

g_nodes = 3
g_edges = 3
k = 2

g_from = [1, 2, 3]
g_to = [2, 3, 1]
g_weight = [4, 5, 3]

Network Diagram

(3)
3 /   \ 5
/     

(1) ———— (2)
4

Explanation

• The network has 3 data centers and 3 bidirectional links:
  • 1 — 2 with latency 4
  • 2 — 3 with latency 5
  • 3 — 1 with latency 3

You need to split this into at most 2 regions (k = 2) by removing links to minimize the maximum latency inside any region.

Optimal Strategy

Remove the connections:

• Between 1 and 2 (latency 4)
• Between 2 and 3 (latency 5)

Now, regions are:

• Region 1: (1, 3) with latency 3
• Region 2: (2) alone

Maximum internal latency among all regions = 3

Output

3