p107.cpp

#include <bits/stdc++.h>
using namespace std;

int costMST(vector<pair<int,int>> graph[], int numVertices) {
    int sumCost = 0;
    priority_queue<pair<int,int>,
        vector<pair<int,int>>,
        greater<pair<int,int>>> pq;
    vector<int> costs(numVertices, INT_MAX);
    vector<bool> visited(numVertices, false);

    int u = 0;
    pq.emplace(0, u);
    costs[u] = 0;

    while (!pq.empty()) {
        auto [cost, node] = pq.top(); pq.pop();
        if (visited[node]) continue;
        visited[node] = true;
        sumCost += cost;

        for (auto& [c, v] : graph[node]) {
            if (!visited[v] && c < costs[v]) {
                costs[v] = c;
                pq.emplace(c, v);
            }
        }
    }

    return sumCost;
}

int main() {
    int numVertices = 40;
    ifstream fs("0107_network.txt");
    vector<pair<int,int>> graph[numVertices];
    string line, field;
    int totalSum = 0;

    for (int i = 0; getline(fs, line); ++i) {
        istringstream sin(line);
        for (int j = 0; getline(sin, field, ','); ++j) {
            if (field != "-") {
                int cost = stoi(field);
                graph[i].emplace_back(cost, j);
                totalSum += cost;
            }
        }
    }
    fs.close();

    int mstWeight = costMST(graph, numVertices);
    int saving = totalSum / 2 - mstWeight;
    cout << saving << endl;
}