PID77 / 恐怖分子
题目描述

一个国家由n个城市组成,任意两个城市间都有一条双向的道路。如今,恐怖分子想要炸掉其中的一些道路,使得这n个城市变得不再连通,也就是说,存在至少两个城市,它们之间不可通过道路互相到达。要炸毁一条道路需要一定的代价。请你计算一下要使恐怖分子达到它们的目的,所需要的最小总代价是多少。

结果说明:破坏道路(1,3),(1,4),(2,3),(2,4)可以使城市1,2与城市3,4之间无法到达,所需的最小总代价为4。

输入格式

第一行为正整数n (n ≤ 50),表示城市的个数,接下来的n行每行由n个0~9之间的数字组成,数字之间没有空格或任何其他字符间隔,第i行的第j个数字表示要破坏城市i与城市j之间的道路所需要的代价。输入数据保证对于任意i, j。第i行的第j个数字与第j行的第i个数相等,且对于所有的i,第i行的第i个数字都等于0。

输出格式

输出仅有一个整数,即要破坏这n个城市的连通性,所需要的最小总代价。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论