2
|
Задача 193. Экономный графпостоянный адрес задачи: http://www.diofant.ru/problem/567/показать код для вставки на свой сайт >> |
Задачу решили:
6
всего попыток:
18
поделиться задачей:
|
|
|
Задача опубликована:
10.09.09 09:02
Прислал:
admin
Источник:
Проект "Эйлер" (http://projecteuler.net)
Вес:
2
сложность:
2
класс:
11 и старше
баллы: 100
Темы:
комбинаторика
,
алгоритмы
|
|
|
На рисунке представлен неориентированный граф, содержащий семь вершин и 12 ребер, суммарный вес которых составляет 243.
Тот же граф можно представить следующей матрицей:
| A | B | C | D | E | F | G | |
| A | - | 16 | 12 | 21 | - | - | - |
| B | 16 | - | - | 17 | 20 | - | - |
| C | 12 | - | - | 28 | - | 31 | - |
| D | 21 | 17 | 28 | - | 18 | 19 | 23 |
| E | - | 20 | - | 18 | - | - | 11 |
| F | - | - | 31 | 19 | - | - | 27 |
| G | - | - | - | 23 | 11 | 27 | - |
Однако, некоторые ребра можно "сэкономить", не нарушая связности графа. Граф, в котором достигается максимальная экономия, представлен ниже. Его вес - всего 93, а "экономия" по сравнению с исходным графом составляет 243-93 = 150.
Пусть задан граф, содержащий 40 вершин, занумерованных числами от 0 до 39. Вес ребра, соединяющего вершины i и j, выражается формулой
wij = wji = (69069(i - j)2(i + j))(mod 1000)
Какой максимальной экономии можно добиться, удаляя лишние ребра без потери связности графа?
Если Вы не можете ее решить, значит Вы не можете ее решить :-)
Обсуждение
Правила >>
у меня 2 вопроса:
1) при некоторых значениях i и j получаются нулевые значения веса ребра. Например, при i=20 и j=0. Это означает что вершины соединены невесомым ребром или же вершины не соединены вовсе?
2) формула для веса ребра wij = 69069*f(i,j) mod 1000. Почему 69069, а не просто 69? Честно говоря, ставит в тупик...
1. Соединены невесомым ребром.
2. Почему вы не сказали раньше? :-)