Что спрашивают
В связанной задаче требуется наибольшее количество рёбер в пути из 11 в 97. Во входе по-прежнему указаны веса, но на ответ они не влияют. Граф ориентированный и ациклический; путь существует.
Количество рёбер — это число переходов. Например, у последовательности из четырёх вершин три ребра. В отличие от задач о сумме весов, итог уже целый: делить его на десять не нужно.
Приём решения
Обозначим через longest(v) наибольшее число переходов от v до финиша. Для финиша это ноль: мы уже на месте. Каждое ребро v → u добавляет ровно один переход, поэтому кандидат равен 1 + longest(u).
Если продолжение от u не ведёт к финишу, его пропускаем. Для недостижимости удобно вернуть None: длинная тупиковая цепочка не должна участвовать в максимуме.
- Из каждой строки возьмём номера начала и конца, а вес прочитаем и отбросим.
- Рекурсивно вычислим лучший результат соседей, добавляя по единице за ребро.
- Выберем максимум, кешируя ответы вершин.
- Выведем ответ для старта без дополнительного округления.
Для наименьшего числа рёбер в том же ациклическом графе достаточно заменить выбор максимума выбором минимума. Начальное значение None, ноль у финиша и прибавление единицы остаются прежними. Для минимума также подходит обход в ширину, если считать каждое ребро одинаковым по стоимости; обычный обход в ширину не решает задачу о максимуме.
Любой путь начинается одним ребром, после которого остаётся путь из соседа. Сравнение величин 1 + longest(u) перебирает все возможные первые шаги. Отсутствие циклов и запоминание дают время и память O(V + E).
Разбор на примере
Ввод
11 97 9.4 11 80 0.2 80 20 0.3 20 97 0.4 11 9 1.0
Вывод
3
- Прямой путь до финиша содержит одно ребро, независимо от его веса
9.4. - Для пути
11 → 80 → 20 → 97получаем снизу вверх: у97ноль, у20один переход, у80два. - У старта лучший допустимый вариант содержит три ребра. Вершина
9до финиша не ведёт. Выводим3; для варианта с минимумом ответ был бы1.
Код на Python и C++
Этот код ищет максимум, как требует задача. Третье поле строки читается в переменную _, поскольку величина веса здесь не используется.
В C++ вес читается в строку weight и дальше не используется, недостижимость — 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, _ = parts
graph.setdefault(int(a), []).append(int(b))
lru_cache(None)
def longest(v):
if v == 97:
return 0
best = None
for u in graph.get(v, []):
tail = longest(u)
if tail is not None:
candidate = 1 + tail
if best is None or candidate > best:
best = candidate
return best
print(longest(11))
<iostream>
<map>
<string>
<vector>
using namespace std;
const long long NO_PATH = -1;
map<int, vector<int>> graph;
void read_graph() {
int a, b;
string weight;
while (cin >> a >> b >> weight)
graph[a].push_back(b);
}
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 (int u : graph[v]) {
long long tail = longest(u);
if (tail != NO_PATH) {
long long candidate = 1 + tail;
if (best == NO_PATH || candidate > best)
best = candidate;
}
}
return memo[v] = best;
}
int main() {
read_graph();
cout << longest(11) << endl;
}
Типичные ошибки
- Складывать веса вместо переходов
Вспомните, какая величина требуется в ответе. Для числа рёбер любой переход добавляет единицу, даже если его вес очень велик.
- Посчитать вершины вместо рёбер
У финиша должно быть ноль оставшихся рёбер. Если вернуть там единицу, результат будет завышен на один.
- Выбрать кратчайший путь
В этой задаче требуется максимум. Минимум числа переходов и максимум числа переходов — разные величины.
- Применить деление из взвешенного шаблона
Здесь нет масштаба десятых долей. Функция сразу возвращает целое количество рёбер, его и нужно вывести.