Что спрашивают

В связанной задаче требуется наибольшее количество рёбер в пути из 11 в 97. Во входе по-прежнему указаны веса, но на ответ они не влияют. Граф ориентированный и ациклический; путь существует.

Количество рёбер — это число переходов. Например, у последовательности из четырёх вершин три ребра. В отличие от задач о сумме весов, итог уже целый: делить его на десять не нужно.

Приём решения

Обозначим через longest(v) наибольшее число переходов от v до финиша. Для финиша это ноль: мы уже на месте. Каждое ребро v → u добавляет ровно один переход, поэтому кандидат равен 1 + longest(u).

Если продолжение от u не ведёт к финишу, его пропускаем. Для недостижимости удобно вернуть None: длинная тупиковая цепочка не должна участвовать в максимуме.

  1. Из каждой строки возьмём номера начала и конца, а вес прочитаем и отбросим.
  2. Рекурсивно вычислим лучший результат соседей, добавляя по единице за ребро.
  3. Выберем максимум, кешируя ответы вершин.
  4. Выведем ответ для старта без дополнительного округления.

Для наименьшего числа рёбер в том же ациклическом графе достаточно заменить выбор максимума выбором минимума. Начальное значение None, ноль у финиша и прибавление единицы остаются прежними. Для минимума также подходит обход в ширину, если считать каждое ребро одинаковым по стоимости; обычный обход в ширину не решает задачу о максимуме.

Любой путь начинается одним ребром, после которого остаётся путь из соседа. Сравнение величин 1 + longest(u) перебирает все возможные первые шаги. Отсутствие циклов и запоминание дают время и память O(V + E).

Разбор на примере

Ориентированный граф из примера; числа на стрелках — веса рёбер9.40.20.30.41.0118020979

Ввод

11 97 9.4
11 80 0.2
80 20 0.3
20 97 0.4
11 9 1.0

Вывод

3
  1. Прямой путь до финиша содержит одно ребро, независимо от его веса 9.4.
  2. Для пути 11 → 80 → 20 → 97 получаем снизу вверх: у 97 ноль, у 20 один переход, у 80 два.
  3. У старта лучший допустимый вариант содержит три ребра. Вершина 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))
#include <iostream>
#include <map>
#include <string>
#include <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;
}

Типичные ошибки

  • Складывать веса вместо переходов

    Вспомните, какая величина требуется в ответе. Для числа рёбер любой переход добавляет единицу, даже если его вес очень велик.

  • Посчитать вершины вместо рёбер

    У финиша должно быть ноль оставшихся рёбер. Если вернуть там единицу, результат будет завышен на один.

  • Выбрать кратчайший путь

    В этой задаче требуется максимум. Минимум числа переходов и максимум числа переходов — разные величины.

  • Применить деление из взвешенного шаблона

    Здесь нет масштаба десятых долей. Функция сразу возвращает целое количество рёбер, его и нужно вывести.