TopCoder problem "Terrorists" used in SRM 334 (Division I Level Three)

Problem Statement

There is a direct bidirectional road between every pair of distinct towns in the country. Terrorists want 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 will be given a String[] roads. The j-th character of the i-th element of roads is a digit representing the cost of blowing up the road from the i-th town to the j-th town. Return the minimal total cost required for the terrorists to achieve their goal.

Definition

Class:	Terrorists
Method:	requiredCost
Parameters:	String[]
Returns:	int
Method signature:	int requiredCost(String[] roads)
(be sure your method is public)

Constraints

roads will contain between 2 and 50 elements, inclusive.

Each element of roads will contain the same number of characters as the number of elements in roads.

Each element of roads will consist of digits ('0' - '9') only.

The i-th character of the j-th element of roads will be equal to the j-th character of the i-th element for all pairs of i and j.

The i-th character of the i-th element of roads will be '0' for all i.

Examples

{"0911",
 "9011",
 "1109",
 "1190"}

Returns: 4

The best decision is to isolate towns 0 and 1 from towns 2 and 3. So, the terrorists should blow up roads (0,2), (0,3), (1,2) and (1,3).

{"0399",
 "3033",
 "9309",
 "9390"}

Returns: 9

The cheapest plan is to isolate town 1. So, the roads to blow up are (1,0), (1,2) and (1,3).

{"030900",
 "304120",
 "040174",
 "911021",
 "027207",
 "004170"}

Returns: 8

{"044967263",
 "409134231",
 "490642938",
 "916036261",
 "634306024",
 "742660550",
 "229205069",
 "633625604",
 "318140940"}

Returns: 27

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7246

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10658&pm=7246

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , brett1479 , Olexiy , marian

Problem categories:

Graph Theory