Week 7 - Assignment 1 - CS103 - Swayam

Week 7 - Assignment 1

Problem Statement

You have been hired as a sewer manager. Your next assignment is to connect all the houses in a village together so that their household sewage can be collected and processed in the village sewage treatment plant. Pipes are expensive, and your department does not get much budget from the government, thus you are to save as much money as possible. As the houses are in a village, the exact locations or coordinates of the houses are not available with you, but you do know how far each house is from each other.

Find out the best way to connect the houses so that their wastes can be plumbed with the least amount of pipes. Each house should be connected to all other houses, directly or indirectly. No house should remain unconnected.

Input Format

The first line of the input contains a single integer t, which is the number of test cases. t test cases follow.

Each test case contains multiple lines.

The first line contains two space-separated integers n and x.

Then n lines follow, each containing n space-separated integers.

Each line represents the distance from that hut to all other huts.

The ith line's jth element represents the distance from hut i to hut j, and is represented as Dij.

The huts are numbered from 1 to n.

Constraints

Output Format

For each test case, output a single integer which is the total cost of laying all the pipes.

Example

Sample Input

1
6 2
0 2 5 6 2 3
2 0 3 3 2 1
5 3 0 2 3 1
6 3 2 0 3 1
2 2 3 3 0 2
3 1 1 1 2 0

Output:

14

Explanation

The given input corresponds to the following configuration of village huts:

Image from Swayam
Figure: Image Taken from Swayam MOOC Course 'Getting Started with Competitive Programming'. All copyrights reserved with Swayam

This can be connected in the following ways:

Image from Swayam
Figure: Image Taken from Swayam MOOC Course 'Getting Started with Competitive Programming'. All copyrights reserved with Swayam

or

Image from Swayam
Figure: Image Taken from Swayam MOOC Course 'Getting Started with Competitive Programming'. All copyrights reserved with Swayam

or

Image from Swayam
Figure: Image Taken from Swayam MOOC Course 'Getting Started with Competitive Programming'. All copyrights reserved with Swayam

Since in all of these three configurations the cost of laying pipes is minimum.

The cost is:

$$(1 + 1 + 1 + 2 + 2) \times 2 = 7 \times 2 = 14$$

Solution

def find_minimum_cost(n, x, distances):
    # Prim's algorithm to find the Minimum Spanning Tree (MST)
    
    # Create a list to track which huts have been added to the MST
    visited = [False] * n  # Initially, no huts are visited
    
    # Create a list to store the minimum edge cost to connect each hut to the MST
    min_edge = [float('inf')] * n  # Start with all edges set to infinity
    
    # Start with the first hut (index 0) and set its minimum edge cost to 0
    min_edge[0] = 0
    
    # Initialize the total cost of the MST
    total_cost = 0

    # Repeat the process n times to ensure all huts are connected
    for _ in range(n):
        # Find the hut with the smallest edge that hasn't been visited yet
        u = -1  # Initialize the variable to track the next hut to add to the MST
        for i in range(n):
            # If the hut hasn't been visited and its edge is the smallest, choose it
            if not visited[i] and (u == -1 or min_edge[i] < min_edge[u]):
                u = i
        
        # Mark this hut as visited (it's now part of the MST)
        visited[u] = True
        
        # Add the cost of this edge to the total MST cost
        total_cost += min_edge[u]

        # For each neighboring hut, update the minimum edge cost to connect it to the MST
        for v in range(n):
            # If the distance to this neighbor is smaller and it's not visited, update
            if distances[u][v] < min_edge[v] and not visited[v]:
                min_edge[v] = distances[u][v]
    
    # The final cost is the total MST cost multiplied by the cost per meter of pipe
    return total_cost * x

def main():
    # Read the number of test cases
    t = int(input())
    
    # Initialize a list to store the results for each test case
    results = []
    
    # Process each test case
    for _ in range(t):
        # Read the number of huts (n) and the cost per meter of pipe (x)
        n, x = map(int, input().split())
        
        # Initialize a list to store the distance matrix for this test case
        distances = []
        
        # Read the distance matrix (n x n)
        for _ in range(n):
            # Read each row of the distance matrix
            distances.append(list(map(int, input().split())))
        
        # Calculate the minimum cost to connect all huts for this test case
        cost = find_minimum_cost(n, x, distances)
        
        # Store the result
        results.append(cost)
    
    # Output all results, one for each test case
    for result in results:
        print(result)

# The entry point of the program
if __name__ == "__main__":
    main()

Explanation

The given problem can be solved using Prim's algorithm to find the Minimum Spanning Tree (MST) of the village huts. The algorithm works by starting with a single hut and adding the next hut with the smallest edge cost until all huts are connected. The total cost of laying pipes is calculated by summing the edge costs of the MST and multiplying by the cost per meter of pipe.

Complexity Analysis

The time complexity of the solution is $O(n^2)$, where $n$ is the number of huts in the village. The space complexity is also $O(n^2)$ to store the distance matrix.

Sample Solution Provided by Instructor