Prim's Algorithm for Minimum Spanning Trees

Prim's algorithm utilizes a distance array where dist[j] represents the shortest distance from node j to the current connected component. The process begins by selecting an arbitrary starting node and initializing distances to all other nodes.

Algorithm Steps:

1. Initialize all distances to infinity except the starting node (distance = 0)
2. Select the closest unvisited node and add it to the connected component
3. Update distances to all adjacent nodes
4. Repeat until all nodes are included

Road Construction Problem

Problem Description

Given n cities with coordinates, the government builds roads in rounds following specific rules:

1. Multiple cities can jointly build the same road
2. Reject the shortest road in any cyclic applications
3. Approve all other valid applications

Cities merge into "alliances" after each round until all cities are connected.

Solution Approach

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX_CITIES = 5010;
struct City {
    double x, y;
};

City cities[MAX_CITIES];
double min_dist[MAX_CITIES];
bool included[MAX_CITIES];

double calculateDistance(double x1, double y1, double x2, double y2) {
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

double findMST(int n) {
    fill(min_dist, min_dist + n + 1, 1e15);
    memset(included, 0, sizeof(included));
    min_dist[1] = 0;
    
    double total_length = 0;
    for (int i = 0; i < n; i++) {
        int current = -1;
        for (int j = 1; j <= n; j++) {
            if (!included[j] && (current == -1 || min_dist[j] < min_dist[current])) {
                current = j;
            }
        }
        
        if (min_dist[current] == 1e15) return -1;
        
        included[current] = true;
        total_length += min_dist[current];
        
        for (int neighbor = 1; neighbor <= n; neighbor++) {
            if (!included[neighbor]) {
                double d = calculateDistance(cities[current].x, cities[current].y, 
                                           cities[neighbor].x, cities[neighbor].y);
                min_dist[neighbor] = min(min_dist[neighbor], d);
            }
        }
    }
    return total_length;
}

int main() {
    int city_count;
    cin >> city_count;
    for (int i = 1; i <= city_count; i++) {
        cin >> cities[i].x >> cities[i].y;
    }
    double result = findMST(city_count);
    printf("%.2lf\n", result);
    return 0;
}

Sample Input

4
0 0
1 2
-1 2
0 4

Sample Output

6.47