Problem 107: Minimal Network

Project Euler Problem 107 Solution

EulerSolve provides an optimized solution for Project Euler Problem 107, Minimal Network, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary The network is given as a symmetric adjacency matrix. Each entry is either a positive integer edge weight or the symbol - for "no direct edge". We want to remove as much total weight as possible while keeping all 40 vertices connected. If $G=(V,E,w)$ is the original weighted graph, the target quantity is the largest possible saving $$\operatorname{saving}=W(G)-W(H),\qquad W(X)=\sum_{e\in E(X)} w(e),$$ where $H$ ranges over connected spanning subgraphs of $G$. The key observation is that an optimal connected network can never contain a cycle. That turns the problem into a minimum spanning tree problem: keep the cheapest possible connected backbone, then subtract its weight from the original total. Mathematical Approach Let $G=(V,E,w)$ be the weighted undirected graph extracted from the matrix, with $n=|V|=40$. The derivation has two distinct parts. First we identify what a minimal network must look like. Then we justify the greedy construction used by the implementations. From a minimal network to a spanning tree Suppose $H$ is a connected spanning subgraph of $G$ with minimum total weight. If $H$ contained a cycle, then deleting any one edge from that cycle would leave all vertices on the cycle still connected through the remaining edges of the cycle. So the graph would stay connected but become strictly lighter....

Detailed mathematical approach

Problem Summary

A network consists of vertices and of edges joining some pairs of them; an edge from $\mathtt A$ to $\mathtt B$ is also an edge from $\mathtt B$ to $\mathtt A$, and each edge has a weight, here a positive whole number. The statement shows a network with seven vertices $\mathtt A,\dots,\mathtt G$ and twelve edges of total weight $243$, also written as a matrix whose entry in row $\mathtt X$ and column $\mathtt Y$ is the weight of the edge between $\mathtt X$ and $\mathtt Y$, or a dash if there is none. Edges may be removed as long as the network stays connected: every vertex must still be reachable from every other one along the remaining edges. In the example the best remaining network weighs $93$, a saving of $243-93=150$. We must find the maximum saving for the forty-vertex network that the 6K text file network.txt gives in the same matrix form. ^[1]

The whole solution in one sentence: the cheapest connected network on all vertices has no closed loop, so it is a tree, and the lightest tree is built by taking the edges from the lightest to the heaviest and keeping each one that joins two parts not yet connected, which is Kruskal's algorithm; the saving is the total weight minus the weight of this tree.

Mathematical Approach

We start with tiny networks, prove that the best network is a tree, and build the lightest tree step by step, proving every step safe.

1. Reading the matrix

Number the vertices $0,1,\dots,n-1$ in the order of the rows, so that $\mathtt A=0$, $\mathtt B=1$, up to $\mathtt G=6$ in the example. The entries at row $i$, column $j$ and at row $j$, column $i$ describe the same edge, so the matrix is symmetric, and we read only the entries with $i\lt j$; each one that is not a dash is an edge. With $w(e)$ the weight of an edge $e$, the total weight of the network $N$ is the sum over all its edges,

$$W(N)=\sum_{e\in N}w(e).$$

Naming an edge by its two ends, the example has, sorted by weight, $w(\mathtt{EG})=11$, $w(\mathtt{AC})=12$, $w(\mathtt{AB})=16$, $w(\mathtt{BD})=17$, $w(\mathtt{DE})=18$, $w(\mathtt{DF})=19$, $w(\mathtt{BE})=20$, $w(\mathtt{AD})=21$, $w(\mathtt{DG})=23$, $w(\mathtt{FG})=27$, $w(\mathtt{CD})=28$ and $w(\mathtt{CF})=31$. These twelve weights are all different, and their sum is $243$. The file's forty lines hold forty comma-separated entries each; the matrix is symmetric with dashes on the diagonal, and $513$ of the $\binom{40}{2}=780$ pairs of vertices are edges, with weights from $1$ to $999$.

2. Tiny networks

Three vertices $\mathtt A$, $\mathtt B$, $\mathtt D$ joined only by $\mathtt{AB}$ and $\mathtt{BD}$ allow no saving: removing either edge cuts a vertex off. Adding $\mathtt{AD}$ makes a triangle of weight $16+17+21=54$. Any two of its edges still connect the three vertices, with weights $33$, $37$ and $38$, but one edge cannot, so the best choice removes the heaviest edge $\mathtt{AD}$ and saves $21$.

Next take $\mathtt A$, $\mathtt B$, $\mathtt D$, $\mathtt E$ with the five edges of the example between them, $\mathtt{AB}$, $\mathtt{BD}$, $\mathtt{DE}$, $\mathtt{BE}$ and $\mathtt{AD}$, of weights $16$, $17$, $18$, $20$ and $21$, together $92$. Four vertices need at least three edges, as Section 3 shows. Of the $\binom53=10$ ways to keep three edges, eight connect all four vertices; the other two, the triangles $\mathtt{ABD}$ and $\mathtt{BDE}$, leave $\mathtt E$ or $\mathtt A$ alone. The lightest of the eight is $\mathtt{AB}$, $\mathtt{BD}$, $\mathtt{DE}$, of weight $51$, and a fourth edge would only add weight, so the saving is $92-51=41=20+21$: each triangle lost its heaviest edge, and no closed loop is left.

3. The best network is a spanning tree

A path follows edges from one vertex to another without visiting any vertex twice, and a cycle is a closed route through at least three vertices that visits no vertex twice except where it starts and ends, like the triangle $\mathtt{ABD}$. Removing an edge of a cycle keeps a connected network connected, and with positive weights it makes the network lighter: if the removed edge joins $u$ and $v$, a walk that used it can go from $u$ to $v$ around the rest of the cycle instead. So the lightest connected network has no cycle: it is a tree, a connected network without cycles, and since it contains all vertices of $N$, a spanning tree of $N$. In a tree two vertices are joined by exactly one path, since two different paths between them would together contain a cycle. ^[2]

Start with $n$ separate vertices, $n$ groups, and add edges one by one. An edge has only two ends, so it lowers the number of groups by one if its ends lie in different groups, and otherwise not at all; its ends share a group exactly when it closes a cycle with the earlier edges. So $n$ vertices need at least $n-1$ edges to be connected, and a spanning tree, whose edges close no cycle, has exactly $n-1$ edges, as it ends with one group. Conversely, if exactly $n-1$ edges connect $n$ vertices, each of them must have joined two groups, so none closed a cycle. Likewise, a network without cycles that has $k$ edges on $n$ vertices has $n-k$ groups.

So the best network keeps $6$ of the $12$ edges of the example and $39$ of the $513$ edges of the file. A spanning tree of least weight is a minimum spanning tree; with positive weights it is exactly a cheapest connected network on all vertices. ^[3] For any minimum spanning tree $T_{\min}$ the maximum saving is

$$S=W(N)-W(T_{\min}),$$

which does not depend on the choice of $T_{\min}$, as all minimum spanning trees have the same least weight.

4. Trying everything

The direct method tries every choice of kept edges. For the example these are $2^{12}=4096$ choices: $1582$ of them connect all seven vertices, $320$ of those have six edges and are the spanning trees, and exactly one is lightest: the edges of weights $11$, $12$, $16$, $17$, $18$ and $19$, together $93$. Kirchhoff's matrix tree theorem counts the spanning trees, ignoring the weights, without listing them: put the degree of each vertex, its number of edges, on the diagonal, $-1$ in row $i$ and column $j$ whenever $i$ and $j$ are joined and $0$ everywhere else, delete one row and the same column, and take the determinant. ^[4] For the triangle $\mathtt{ABD}$ of Section 2, where every vertex has degree $2$, the matrix is

$$\begin{pmatrix}2&-1&-1\\-1&2&-1\\-1&-1&2\end{pmatrix}.$$

Deleting its last row and column leaves the rows $(2,-1)$ and $(-1,2)$; a matrix with rows $(a,b)$ and $(c,d)$ has determinant $ad-bc$, here $2\cdot2-(-1)\cdot(-1)=3$: the three trees of weights $33$, $37$ and $38$ found there. For the example, where all degrees are $3$ except the $6$ of $\mathtt D$, the theorem gives $320$ again. For the file it gives a $54$-digit number, about $3.85\cdot10^{53}$, and its edges can be kept or removed in $2^{513}\gt10^{154}$ ways: far too many to try.

5. The exchange step and the cut rule

All proofs below use one move. Removing an edge $f$ from a spanning tree $T$ leaves $n-2$ edges without a cycle, hence two groups by Section 3; if an edge $e$ joins them, then $T-f+e$, the tree with $f$ replaced by $e$, is connected with $n-1$ edges, a spanning tree of weight $W(T)-w(f)+w(e)$. In the triangle of Section 2, removing $\mathtt{AD}$ from the tree $\mathtt{AB}$, $\mathtt{AD}$ of weight $37$ leaves the groups $\mathtt{AB}$ and $\mathtt D$, and $\mathtt{BD}$ joins them: the tree $\mathtt{AB}$, $\mathtt{BD}$ weighs $37-21+17=33$.

Split the vertices into two non-empty groups $X$ and $Y$; an edge with one end in each group crosses this cut. The cut rule: a lightest crossing edge $e$ lies in some minimum spanning tree, and in all of them if every other crossing edge is strictly heavier. ^[3] For the proof, let $T$ be a minimum spanning tree without $e$. The only path in $T$ between the ends of $e$ leads from $X$ to $Y$, so one of its edges $f$ crosses the cut, and removing $f$ separates the ends of $e$, since a path between them avoiding $f$ would be a second path in $T$. So $T-f+e$ is a spanning tree, and $w(e)\le w(f)$ makes it a minimum spanning tree that contains $e$; if $w(e)\lt w(f)$, it would even be lighter than $T$, which is impossible. In the example the edges at $\mathtt F$ weigh $31$, $19$ and $27$, so $\mathtt{DF}$, the lightest, lies in every minimum spanning tree.

6. Kruskal's algorithm

Kruskal's algorithm sorts the edges by weight, puts every vertex in a group of its own, and goes through the edges from the lightest: an edge joining two different groups is kept, and its groups are merged; any other edge would close a cycle and is skipped. ^[5] It stops when $n-1$ edges are kept. We show below that every edge it keeps passes the cut rule. In the example the groups after each kept edge are:

$\mathtt{EG}$ ($11$): $\mathtt{EG}$, $\mathtt A$, $\mathtt B$, $\mathtt C$, $\mathtt D$, $\mathtt F$;
$\mathtt{AC}$ ($12$): $\mathtt{AC}$, $\mathtt{EG}$, $\mathtt B$, $\mathtt D$, $\mathtt F$;
$\mathtt{AB}$ ($16$): $\mathtt{ABC}$, $\mathtt{EG}$, $\mathtt D$, $\mathtt F$;
$\mathtt{BD}$ ($17$): $\mathtt{ABCD}$, $\mathtt{EG}$, $\mathtt F$;
$\mathtt{DE}$ ($18$): $\mathtt{ABCDEG}$, $\mathtt F$;
$\mathtt{DF}$ ($19$): all seven vertices in one group.

The six kept edges weigh $93$, and the saving is $243-93=150$. Had we not stopped, the next edge $\mathtt{BE}$ ($20$) would be skipped: $\mathtt B$ and $\mathtt E$ are already joined by the kept edges $\mathtt{BD}$ and $\mathtt{DE}$, so $\mathtt{BE}$ would close the cycle $\mathtt{BDE}$. In the file the tree is complete after the $51$ lightest of the $513$ edges, $12$ of which are skipped.

Every kept edge is safe: the kept edges always lie in some minimum spanning tree. This holds at the start. Suppose they lie in a minimum spanning tree $T$ and the next kept edge $e$ leaves the group $X$. An earlier edge leaving $X$ would have joined two groups when examined, since groups only merge, so it would have been kept and would now lie inside one group. So $e$ is a lightest edge of the cut between $X$ and the rest; for $\mathtt{DE}$, with $X=\mathtt{ABCD}$, the crossing edges weigh $18$, $19$, $20$, $23$ and $31$. If $T$ lacks $e$, the proof of the cut rule puts $e$ in place of an edge $f$ of $T$ that leaves $X$ and so is not kept; either way a minimum spanning tree contains $e$ and all kept edges. If several groups were left at the end, an edge of the connected network between two of them would have been kept when examined; so one group is left, and the $n-1$ kept edges form a spanning tree inside a minimum spanning tree, hence equal to it.

7. Merging groups quickly: union–find

To test whether two vertices share a group, the programs use a disjoint-set structure, or union–find. ^[6] Every vertex stores a parent, another vertex of its group or itself, and following parents leads to the root that represents the group: find returns this root, and union makes one root the parent of the other. Every vertex starts as a root of rank $0$. Union by rank hangs the root of smaller rank below the other, and equal ranks make the rank of the new root grow by one; in both cases the rank of a root stays at least the height of its tree of parent links. A root of rank $r$ has at least $2^r$ vertices in its group, as it reaches rank $r+1$ only by taking in another root of rank $r$, so a find takes at most $\log_2 n$ steps, at most $5$ for forty vertices. Path compression, in C++, points every vertex passed by a find straight to the root; path halving, in Python and Java, points every other one to its grandparent; both only shorten paths. With union by rank, either costs $O(\alpha(n))$ amortised time per operation, where $O(x)$ means at most a constant times $x$ and amortised means averaged over any sequence of operations, even the worst one; a single operation may take longer. The inverse Ackermann function $\alpha$ is at most $4$ for any practical $n$.

In the example, with the C++ rules, $\mathtt G$ points to $\mathtt E$ and $\mathtt C$ to $\mathtt A$, both roots getting rank $1$; then $\mathtt B$ and $\mathtt D$ point to $\mathtt A$; for $\mathtt{DE}$ the roots $\mathtt A$ and $\mathtt E$ have equal ranks, so $\mathtt E$ points to $\mathtt A$, which gets rank $2$; finally $\mathtt F$ points to $\mathtt A$. Every vertex now reaches $\mathtt A$ in at most two steps. These parent links are bookkeeping only and need not be edges of the network (there is no edge $\mathtt{AE}$); the spanning tree is the list of kept edges.

8. Removing from the top: the cycle rule

The problem's wording suggests another method, based on the cycle rule: an edge heavier than every other edge of some cycle lies in no minimum spanning tree. ^[3] If a minimum spanning tree $T$ contained such an edge $e$, removing $e$ would leave two groups, the rest of the cycle would have an edge $f$ joining them, and $T-e+f$ would be lighter than $T$. The reverse-delete algorithm takes the edges from the heaviest, tied edges in any fixed order, and deletes each one whose removal leaves the network connected; it ends with a minimum spanning tree. ^[7] In the example it deletes $\mathtt{CF}$, $\mathtt{CD}$, $\mathtt{FG}$, $\mathtt{DG}$, $\mathtt{AD}$ and $\mathtt{BE}$, each the heaviest edge of a cycle still present ($\mathtt{CDF}$, $\mathtt{ACD}$, $\mathtt{DFG}$, $\mathtt{DEG}$, $\mathtt{ABD}$, $\mathtt{BDE}$); then every remaining edge is needed. The deleted weights add up to $31+28+27+23+21+20=150$.

With tied weights the cycle rule does not cover every deletion: in a triangle with weights $1$, $2$, $2$, whichever edge of weight $2$ comes first is deleted, although it lies in a minimum spanning tree. So the proof shows instead that the remaining network always contains some minimum spanning tree $T$. An edge $e$ is deleted only if the network stays connected, so $e$ lies on a cycle of it. Every other edge of this cycle is still unexamined, as it would have been deleted when examined, the whole cycle being present then; so it weighs at most $w(e)$. If $e$ lies in $T$, one of these edges, $f$, joins the two groups left by removing $e$ from $T$, and $T-e+f$, of weight at most $W(T)$, is a minimum spanning tree that survives the deletion. In the end no cycle is left: a cycle still there would have been present all along, so its first examined edge would have been deleted. The result is therefore a spanning tree containing a minimum spanning tree, hence equal to it. On the file it keeps the same $39$ edges as Kruskal's algorithm, since by Section 9 there is only one minimum spanning tree. Done simply, every trial deletion is followed by a search through the remaining network, which costs $O(n+m)$ for $m$ edges, so $O(m(n+m))$ in all, far more than the sorting in Kruskal's algorithm.

9. One best network or several?

Distinct weights make the minimum spanning tree unique, ^[3] but the file has only $406$ different weights among its $513$ edges. A test that also works with ties: if every edge outside a spanning tree $T$ is strictly heavier than all edges of the path in $T$ between its ends, $T$ is the only minimum spanning tree. For another spanning tree $T'$, take an edge $f$ of $T'$ outside $T$. Removing $f$ from $T'$ leaves two groups, and the path in $T$ between the ends of $f$ crosses between them along an edge $e$ of $T$, which is not in $T'$, since $f$ was its only edge between the groups, and $w(e)\lt w(f)$. So $T'-f+e$ is lighter than $T'$: no tree but $T$ is minimal. The word strictly matters: a triangle with weights $1$, $2$, $2$ has two lightest trees of weight $3$, and the test fails, as the outside $2$ is not strictly heavier than the $2$ on its tree path; with weights $1$, $1$, $2$ a weight repeats, but the lightest tree is unique and the test passes. A separate check confirms the test for all $474$ outside edges of the file, so its best network is unique too.

10. Prim's algorithm and some pitfalls

Prim's algorithm, found by Jarník in 1930 and later by Prim and by Dijkstra, grows one tree from a start vertex, always adding the lightest edge from the tree to a new vertex, which the cut rule makes safe. ^[8] From $\mathtt A$ it adds $\mathtt{AC}$, $\mathtt{AB}$, $\mathtt{BD}$, $\mathtt{DE}$, $\mathtt{EG}$ and $\mathtt{DF}$, the same tree. If every outside vertex remembers its lightest edge to the tree, each step picks the outside vertex with the lightest remembered edge and then scans that vertex's row of the matrix to update the others: two scans of length $n$ per step, $O(n^2)$ in all. ^[8] Some pitfalls:

Every edge must be counted once: the sum of all matrix entries of the example is $486$, and $486-93=393$ is not the saving.
With negative weights the best network need not be a tree: in a triangle of three edges of weight $-1$, keeping all three gives $-3$, less than the $-2$ of any spanning tree.
A disconnected network cannot be made connected; Kruskal's algorithm then returns a minimum spanning forest, one tree per connected part. ^[5]

How the Code Works

The C++ program ^[9] reads its options in parse_arguments: --skip-checkpoints turns off the self-check, and --file= followed by a path replaces the default input, 0107_network.txt in the folder resources/documents. run_checkpoints then requires the saving $150$ for the matrix of the statement, stored in the source as a string, and solve hands the text of the file to solve_from_text; an unknown option, a failed checkpoint and errors such as a missing file give the exit codes $1$, $2$ and $3$.

solve_from_text splits the text into lines, skipping empty ones, and the lines at the commas, and rejects a row whose length differs from the number $n$ of rows. For $j\gt i$, as in Section 1, it skips dashes, converts the other entries with std::stoi, adds them to total_weight, a long long, and stores each edge as an Edge; std::sort orders the edges by weight. DisjointSet implements Section 7: std::iota makes every vertex its own parent, find is recursive with path compression, and unite merges by rank, returning false when the two roots coincide. The loop of Section 6 adds the weight of each edge accepted by unite to mst_weight and stops after $n-1$ edges; total_weight - mst_weight is the saving $S$.

Python's solve looks for the data file in resources/documents one level above the folder of the script, and Java's main, like C++, relative to the working directory. Python keeps the edges as tuples (w, i, j), which edges.sort() orders by weight and then by their ends; Java keeps them as three-element int[] arrays in an ArrayList, sorted by the weight alone. Both use path halving in find and union by rank in union, and scan all $513$ edges instead of stopping after $51$, which changes nothing, as every later edge is skipped like $\mathtt{BE}$ in Section 6. Lines are read differently: Python strips each line and skips empty ones; Java keeps empty lines, so an extra blank line at the end of the file stops it with an index error; C++ skips empty lines, but on Linux and macOS it keeps the carriage return of Windows line endings, so a dash ending a row is not recognised and the program exits with code $3$; on Windows the file stream, opened in text mode, drops these carriage returns. The file used here has neither problem. The totals stay below $780\,000$ for forty vertices with weights below $1000$, so Java's int totals suffice; C++ adds its int weights into long long totals, and Python's integers have no size limit. Only the C++ program checks itself, and none checks connectivity; a disconnected input would silently give the saving of a minimum spanning forest. With tied weights the programs may build different trees of equal weight; here the tree is unique, by Section 9.

Complexity and Verification

With $n$ vertices and $m$ edges, reading the matrix touches $n^2$ entries, sorting costs $O(m\log m)$ and union–find $O(m\,\alpha(n))$, so a run takes $O(n^2+m\log m)$ time, which is $O(n^2\log n)$ for a nearly full matrix. ^[5] The memory is $O(n^2)$ for the text and $O(m+n)$ for the edges and groups. With $1600$ entries and $513$ edges, tests on a current computer took about $2$ milliseconds for the C++ program and about $15$ and $30$ milliseconds for the Python and Java programs, mostly the start-up time of Python and of the Java virtual machine.

Unless --skip-checkpoints is given, the C++ program checks on every start that the example gives $150$. The checks made for this article are not part of the published programs. All three programs print the same number for the file, and for $300$ random connected networks with up to $7$ vertices and $13$ edges, many with tied weights, they agree with an enumeration of all edge subsets. A separate program recomputed every number quoted above for the example and the file, and Prim's algorithm gives the same tree weight on the file; altered copies of the file confirm the line handling described above.

Footnotes and References

The references below supply the background facts used above.

Project Euler 107 — Minimal Network. The official statement: a seven-vertex network of twelve edges and total weight 243, also given as a matrix, can be optimised to weight 93, a saving of 150; the task asks for the maximum saving for the forty-vertex network in network.txt while the network remains connected.
Wikipedia — Tree (graph theory). A tree is a connected acyclic undirected graph; any two of its vertices are joined by exactly one path, and a connected graph on n vertices is a tree exactly when it has n − 1 edges.
Wikipedia — Minimum spanning tree. With positive weights a minimum spanning tree is a minimum-cost subgraph connecting all vertices. The article states the cut property, the cycle property and the uniqueness of the tree when all edge weights are distinct.
Wikipedia — Kirchhoff's theorem. The number of spanning trees equals any cofactor of the Laplacian matrix, the degree matrix minus the adjacency matrix; it is also called the matrix tree theorem.
Wikipedia — Kruskal's algorithm. Edges are added in order of increasing weight unless they form a cycle, with a disjoint-set data structure; a disconnected graph gives a minimum spanning forest, and the sorting dominates the running time O(E log E).
Wikipedia — Disjoint-set data structure. Find follows parent pointers to the root, and union links two roots. With union by rank and path compression or path halving, each operation takes Θ(α(n)) amortised time, as Tarjan proved, and α(n) is at most 4 for any practical n.
Wikipedia — Reverse-delete algorithm. The edges are examined in order of decreasing weight, and each one whose removal keeps the graph connected is deleted; it first appeared in Kruskal's 1956 paper, and the article proves its correctness.
Wikipedia — Prim's algorithm. The algorithm grows a tree from an arbitrary vertex by the cheapest connection to another vertex; Jarník found it in 1930, Prim in 1957 and Dijkstra in 1959, and with an adjacency matrix it takes O(|V|²) time.
C++ — Euler107.cpp. The linked immutable C++ revision contains DisjointSet, solve_from_text, run_checkpoints and the options --skip-checkpoints and --file=; it is the implementation record for this article.

Problem 107 source code

C++

#include <algorithm>
#include <fstream>
#include <iostream>
#include <numeric>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>

namespace {

struct Options {
    std::string file = "resources/documents/0107_network.txt";
    bool run_checkpoints = true;
};

struct Edge {
    int u = 0;
    int v = 0;
    int w = 0;
};

struct DisjointSet {
    std::vector<int> parent;
    std::vector<int> rank;

    explicit DisjointSet(int n) : parent(static_cast<std::size_t>(n)), rank(static_cast<std::size_t>(n), 0) {
        std::iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[static_cast<std::size_t>(x)] != x) {
            parent[static_cast<std::size_t>(x)] = find(parent[static_cast<std::size_t>(x)]);
        }
        return parent[static_cast<std::size_t>(x)];
    }

    bool unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return false;
        }
        if (rank[static_cast<std::size_t>(a)] < rank[static_cast<std::size_t>(b)]) {
            std::swap(a, b);
        }
        parent[static_cast<std::size_t>(b)] = a;
        if (rank[static_cast<std::size_t>(a)] == rank[static_cast<std::size_t>(b)]) {
            ++rank[static_cast<std::size_t>(a)];
        }
        return true;
    }
};

bool parse_string_after_prefix(const std::string& arg,
                               const std::string& prefix,
                               std::string& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    value = tail;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_string_after_prefix(arg, "--file=", options.file)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return true;
}

long long solve_from_text(const std::string& text) {
    std::istringstream input(text);
    std::string line;
    std::vector<std::vector<std::string>> rows;

    while (std::getline(input, line)) {
        if (line.empty()) {
            continue;
        }
        std::vector<std::string> row;
        std::istringstream row_input(line);
        std::string token;
        while (std::getline(row_input, token, ',')) {
            row.push_back(token);
        }
        rows.push_back(row);
    }

    const int n = static_cast<int>(rows.size());
    std::vector<Edge> edges;
    long long total_weight = 0;

    for (int i = 0; i < n; ++i) {
        if (static_cast<int>(rows[static_cast<std::size_t>(i)].size()) != n) {
            throw std::runtime_error("Malformed network matrix");
        }
        for (int j = i + 1; j < n; ++j) {
            const std::string& token = rows[static_cast<std::size_t>(i)][static_cast<std::size_t>(j)];
            if (token == "-") {
                continue;
            }
            const int w = std::stoi(token);
            total_weight += w;
            edges.push_back({i, j, w});
        }
    }

    std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w < b.w; });

    DisjointSet dsu(n);
    long long mst_weight = 0;
    int used = 0;

    for (const Edge& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mst_weight += e.w;
            ++used;
            if (used == n - 1) {
                break;
            }
        }
    }

    return total_weight - mst_weight;
}

long long solve(const std::string& file_path) {
    std::ifstream input(file_path);
    if (!input) {
        throw std::runtime_error("Could not open network file: " + file_path);
    }

    std::ostringstream buffer;
    buffer << input.rdbuf();
    return solve_from_text(buffer.str());
}

bool run_checkpoints() {
    const std::string sample =
        "-,16,12,21,-,-,-\n"
        "16,-,-,17,20,-,-\n"
        "12,-,-,28,-,31,-\n"
        "21,17,28,-,18,19,23\n"
        "-,20,-,18,-,-,11\n"
        "-,-,31,19,-,-,27\n"
        "-,-,-,23,11,27,-\n";

    if (solve_from_text(sample) != 150) {
        std::cerr << "Checkpoint failed for statement sample network" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    try {
        std::cout << solve(options.file) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 3;
    }

    return 0;
}

Python

# Problem 107: Minimal network
# Find the maximum saving by removing redundant edges (MST).

import os

def solve():
    script_dir = os.path.dirname(os.path.abspath(__file__))
    file_path = os.path.join(script_dir, '..', 'resources', 'documents', '0107_network.txt')
    with open(file_path) as f:
        lines = [line.strip() for line in f if line.strip()]
    
    n = len(lines)
    edges = []
    total_weight = 0
    for i in range(n):
        parts = lines[i].split(',')
        for j in range(i+1, n):
            if parts[j] != '-':
                w = int(parts[j])
                edges.append((w, i, j))
                total_weight += w
    
    # Kruskal's MST
    edges.sort()
    parent = list(range(n))
    rank = [0] * n
    
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry: return False
        if rank[rx] < rank[ry]: rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]: rank[rx] += 1
        return True
    
    mst_weight = 0
    for w, u, v in edges:
        if union(u, v):
            mst_weight += w
    
    print(total_weight - mst_weight)

solve()

Java

import java.nio.file.*;
import java.util.*;

public class Euler107 {
    static int[] parent, rank_;

    static int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    static boolean union(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry)
            return false;
        if (rank_[rx] < rank_[ry]) {
            int t = rx;
            rx = ry;
            ry = t;
        }
        parent[ry] = rx;
        if (rank_[rx] == rank_[ry])
            rank_[rx]++;
        return true;
    }

    public static void main(String[] args) throws Exception {
        List<String> lines = Files.readAllLines(Path.of("resources/documents/0107_network.txt"));
        int n = lines.size();
        List<int[]> edges = new ArrayList<>();
        int totalW = 0;
        for (int i = 0; i < n; i++) {
            String[] p = lines.get(i).split(",");
            for (int j = i + 1; j < n; j++)
                if (!p[j].equals("-")) {
                    int w = Integer.parseInt(p[j]);
                    edges.add(new int[] { w, i, j });
                    totalW += w;
                }
        }
        edges.sort((a, b) -> a[0] - b[0]);
        parent = new int[n];
        rank_ = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
        int mstW = 0;
        for (int[] e : edges)
            if (union(e[1], e[2]))
                mstW += e[0];
        System.out.println(totalW - mstW);
    }
}