Задача Om. Радіоінженер-проектувальник Василь Петрович намалював складну електричну схему з резисторів відомих йому опорів, що з’єднують контактні площадки його монтажної плати. Площадки можуть бути з’єднані між собою тільки резисторами. Гарантовано, що існує електричний зв’язок між будь-якою парою площадок. Потім Василь Петрович розпочав по одному випаювати резистори з схеми, але так, аби не порушилася попередня гарантія. Допоможіть йому це зробити так, щоб сумарний опір резисторів, що залишаться, був мінімальний (мається на увазі мінімальна сума номіналів резисторів, що залишаться при умові існування електричного зв’язку між усіма площадками).
|
Приклад
|
|
Введення
|
Виведення
|
|
4
|
|
|
|
|
0
|
3
|
1
|
2
|
|
3
|
0
|
5
|
0
|
|
1
|
5
|
0
|
0
|
|
2
|
0
|
0
|
0
|
|
6
|
Технічні умови. Програма Om читає з клавіатури (пристрою стандартного введення) кількість контактних площадок N (до них припаюють кінці резисторів) (3≤N≤1000), а далі N рядків по N чисел Ri.j в кожному (0≤ Ri.j ≤1000) – опір резистора між i-ою таj-ою площадками. Якщо між даною парою площадок резистора немає, Ri.j =0 (тут цифра 0 означає просто відсутність резистора, а не опір рівний 0!)
Програма виводить на екран (пристрій стандартного виведення) єдине число – мінімально можливу суму опорів резисторів, що залишаться.
|
