Watering Fields
InterviewTime limit2sMemory limit128 MB
Given well-digging costs per field and pairwise pipe-connection costs, compute the minimum total cost to give every field water using an MST-style approach with a virtual water source.
- Level
Medium5 of 10
- Topics
- Minimum spanning tree, Graph, Greedy
- Solved
- No attempts yet
Problem
A farmer wants to supply water to all N fields. There are two ways to do this. A well can be dug directly in a field, or water can be brought from another field that already has water by connecting the two fields.
You are given the cost of digging a well in each field and the cost of connecting each pair of fields. Find the minimum total cost needed to supply water to every field.
Input
The first line contains the number of fields N.
The next N lines contain the costs Wi in order, where Wi is the cost of digging a well in field i.
The following N lines each contain N integers. The j-th integer on the i-th of these lines, Pi,j, is the cost of connecting field i and field j with a waterway.
The conditions are as follows.
- 1 ≤ N ≤ 300
- 1 ≤ Wi ≤ 100,000
- 1 ≤ Pi,j ≤ 100,000 (i ≠ j)
- Pi,j = Pj,i
- Pi,i = 0
Output
Print the minimum cost required to supply water to every field.