Что спрашивают
Найдите путь из 11 в 97 с наибольшей суммой весов и выведите целую часть этой суммы. Граф ориентированный, без циклов; путь до заданного финиша существует.
Здесь важно слово «до финиша». Длинная ветвь, которая заканчивается в другой вершине, не является решением. Также максимальная сумма весов не обязательно достигается на пути с наибольшим числом рёбер.
Приём решения
Пусть longest(v) — наибольшая длина продолжения из v до 97. Для финиша значение равно нулю. Для другой вершины перебираем рёбра v → u и выбираем максимум из w + longest(u), но только если продолжение от u до финиша существует.
Недостижимость обозначим None. Начинать лучший результат с нуля опасно: тогда вершина в тупике выглядит как допустимый конец пути. Большое ребро в такой тупик может дать ложный максимум.
- Прочитаем граф и переведём веса в целые десятые доли.
- В рекурсии вернём ноль только на заданном финише.
- Пропустим все продолжения со значением
None, из остальных выберем максимум. - Запомним ответ каждой вершины и выведем целую часть итоговой суммы.
Доказательство такое же, как для кратчайшего пути: любой путь имеет первое ребро и некоторое продолжение, а рекурсия выбирает лучшее продолжение для каждого первого шага. Отличается только операция выбора — максимум вместо минимума.
Линейная динамика здесь возможна благодаря отсутствию циклов. Этот код нельзя без изменений переносить на произвольный граф с циклами. В данных условиях время — O(V + E), память — O(V + E).
Разбор на примере
Ввод
11 97 4.2 11 80 1.1 80 20 1.4 20 97 1.2 11 9 90.0
Вывод
4
- У финиша значение ноль. Через
20до него остаётся1.2, через80—1.4 + 1.2 = 2.6. - Из старта сравниваем прямой путь длины
4.2и путь с несколькими рёбрами длины1.1 + 2.6 = 3.7. - Ветвь в
9имеет большой вес, но не достигает финиша. Её исключаем. Наибольшая допустимая длина —4.2, целая часть —4.
Код на Python и C++
Знак сравнения при выборе лучшего результата — >. Значение None отделяет недостижимый финиш от пути нулевой длины.
В C++ недостижимость обозначена NO_PATH = -1. Такие продолжения пропускаются до сравнения, поэтому минус единица не может победить настоящий путь.
import sys
from functools import lru_cache
sys.setrecursionlimit(5000)
graph = {}
for line in sys.stdin:
parts = line.split()
if not parts:
continue
a, b, text = parts
whole, tenth = text.split('.')
weight = int(whole) * 10 + int(tenth)
graph.setdefault(int(a), []).append((int(b), weight))
lru_cache(None)
def longest(v):
if v == 97:
return 0
best = None
for u, w in graph.get(v, []):
tail = longest(u)
if tail is not None:
candidate = w + tail
if best is None or candidate > best:
best = candidate
return best
print(longest(11) // 10)
<iostream>
<map>
<string>
<utility>
<vector>
using namespace std;
const long long NO_PATH = -1;
map<int, vector<pair<int, long long>>> graph;
void read_graph() {
int a, b;
string text;
while (cin >> a >> b >> text) {
size_t dot = text.find('.');
long long weight = stoll(text.substr(0, dot)) * 10 + stoll(text.substr(dot + 1));
graph[a].push_back({b, weight});
}
}
map<int, long long> memo;
long long longest(int v) {
if (v == 97)
return 0;
if (memo.count(v))
return memo[v];
long long best = NO_PATH;
for (auto [u, w] : graph[v]) {
long long tail = longest(u);
if (tail != NO_PATH) {
long long candidate = w + tail;
if (best == NO_PATH || candidate > best)
best = candidate;
}
}
return memo[v] = best;
}
int main() {
read_graph();
cout << longest(11) / 10 << endl;
}
Типичные ошибки
- Оставить минимум от шаблона кратчайшего пути
Все переходы остаются похожими, но операция выбора меняется. Проверьте знак сравнения и смысл возвращаемой величины.
- Принимать любой тупик за финиш
Путь должен заканчиваться именно в заданной вершине. Большой вес ветви не делает её допустимой.
- Максимизировать число переходов
Веса могут различаться. Сравнивайте суммы весов, если условие спрашивает длину взвешенного пути.
- Отбрасывать дробные части рёбер
Целая часть суммы вычисляется после выбора полного пути. Округление рёбер меняет сравниваемые длины.