Terrorists

SRM 334 · 2007-01-13 · by Andrew_Lazarev

SRM 334 · 2007-01-13 · by Andrew_Lazarev · Graph Theory

Show categories

Class Name: Terrorists

Return Type: int

Method Name: requiredCost

Arg Types: (vector<string>)

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.

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

{"0478122019605605828","4040491862401574068","7404844408554400297","8040838953363789153","1488086662874379878","2943807364286037863","2148670303668783223","0849633082274287443","1605660802489151560","9283243220748921785","6453826247055007108","0056786784508094540","5143468498580267507","6547307219002018089","0708738852096104849","5409973711747840242","8021882457155082070","2695762468040844702","8873833305807992020"}
Returns: 72

{"015841332118037473232854998290704","102151536070178436260674855238507","520588854293384787157459848840928","815049593606012999218708943374715","458409402675555828250728077873615","118990477017587667999778908138762","358544028751994205302062850334323","335907204281268202212644095172922","264327840730356551418190620766685","102660727094706277473197463387302","179071583904521121115078973534980","803657110440594184216249400131043","013055923755020332194219313539504","378158965029201515986470095129584","784257486614010359900921548014153","447986225211353026698550558638748","738926005728315200933949512570960","367987521714259600638013778200505","221229324412199696039221471220962","365159011711980933307087559152024","207809228356460838970901798150875","864777061102249590209081514238836","575027649974172541280800096248409","449888240789901093171100198709321","988909806494305557457501082562268","954470592670194517759199807884283","858378050330358828198468270362813","228381317351510652211227583024333","934773376833321370255340686204314","080438426741994800020889242440176","759767396390551795908843228331006","002116228084085460627302681317002","478552325203443805245691833346620"}
Returns: 105

Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Terrorists with a public method int requiredCost(vector<string> roads) · 59 test cases · 2 s / 256 MB per case