Maximum flow and matchings
Blowing up the roads
There is a direct bidirectional road between every pair of distinct towns in the country. Peter wants to blow up enough of these roads that there are at least two towns that are no longer connected to each other by any direct or indirect paths.
You are given the cost of blowing up each road. Find the minimal total cost required for Peter to achieve their goal.
Consists of multiple test cases. The first line of each test case contains the number n (n ≤ 50) of towns in a country. Next n lines describe the roads: the j-th character of the i-th line is a digit representing the cost of blowing up the road from the i-th town to the j-th town.
For each test case print in a separate line the minimal total cost required for Peter to achieve their goal.
4 0911 9011 1109 1190 6 030900 304120 040174 911021 027207 004170 4 0399 3033 9309 9390
4 8 9