16.2 Динамическое программирование на ориентированных графах

Идея раздела

Если ориентированный граф ацикличен, то есть в нём нет направленных циклов, на нём очень удобно запускать динамическое программирование.

Почему это работает? Потому что в DAG можно упорядочить вершины так, чтобы все рёбра шли только слева направо по этому порядку. Такой порядок называется топологической сортировкой. После этого каждая вершина зависит только от уже посчитанных вершин, а значит, значения динамики можно вычислять последовательно.

Это одна из самых полезных идей в олимпиадном программировании:

• если состояние зависит только от более «ранних» состояний,
• и между зависимостями нет циклов,
• значит, почти наверняка можно построить DP.

---

Что можно считать с помощью DP на DAG

Пусть есть стартовая вершина s и финишная вершина t. Тогда на DAG часто можно эффективно найти:

• число различных путей из s в t;
• длину кратчайшего пути;
• длину самого длинного пути;
• минимальное или максимальное количество рёбер в пути;
• вершины, которые обязаны встречаться в любом пути;
• количество кратчайших путей, если сначала построить DAG кратчайших переходов.

Главная мысль: мы выбираем, что именно будет хранить dp[v], а затем пишем переходы по рёбрам графа.

---

Когда это работает

DP в таком виде работает именно на ацикличном ориентированном графе.

Если в графе есть цикл, то ситуация может стать зацикленной:

• значение в вершине u зависит от v,
• значение в v зависит от w,
• значение в w снова зависит от u.

Тогда простой линейный порядок вычисления ломается.

Поэтому стандартный план такой:

1. Проверить, что граф ацикличен, или получить DAG по условию задачи.
2. Построить топологический порядок вершин.
3. Запускать DP по этому порядку.

---

Базовый пример: подсчёт количества путей

Рассмотрим ориентированный ацикличный граф.

Пусть нужно посчитать количество путей из вершины 1 в вершину 6.

Возьмём такой граф:

• 1 -> 2
• 1 -> 4
• 4 -> 5
• 5 -> 2
• 5 -> 3
• 2 -> 3
• 3 -> 6

Из вершины 1 в вершину 6 есть три пути:

• 1 -> 2 -> 3 -> 6
• 1 -> 4 -> 5 -> 2 -> 3 -> 6
• 1 -> 4 -> 5 -> 3 -> 6

Как задать динамику

Пусть dp[v] — количество путей из стартовой вершины 1 в вершину v.

Тогда:

• dp[1] = 1, потому что есть ровно один способ «добраться» до старта: уже находиться в нём;
• для любой другой вершины v:

dp[v] = сумма dp[u] по всем рёбрам u -> v

Идея очень естественная: каждый путь в v должен прийти в неё из какой-то предыдущей вершины u.

Почему это корректно

Каждый путь в v заканчивается последним ребром u -> v.

Если мы знаем количество путей до всех таких u, то можем просто сложить эти количества. При этом пути не пересекаются по последнему ребру как объекты подсчёта, поэтому двойного счёта нет.

---

Решение через обход по топологическому порядку

Обычно удобнее хранить граф по исходящим рёбрам и распространять значения вперёд.

Если есть ребро v -> to, то каждое достижение v даёт новое достижение to.

Тогда переход выглядит так:

dp[to] += dp[v]

Если обрабатывать вершины в топологическом порядке, то к моменту обработки v значение dp[v] уже полностью посчитано.

Код на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 6;
    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);

    auto add_edge = [&](int a, int b) {
        g[a].push_back(b);
        indeg[b]++;
    };

    add_edge(1, 2);
    add_edge(1, 4);
    add_edge(4, 5);
    add_edge(5, 2);
    add_edge(5, 3);
    add_edge(2, 3);
    add_edge(3, 6);

    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) q.push(v);
    }

    vector<int> topo;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        topo.push_back(v);
        for (int to : g[v]) {
            indeg[to]--;
            if (indeg[to] == 0) q.push(to);
        }
    }

    vector<long long> dp(n + 1, 0);
    dp[1] = 1;

    for (int v : topo) {
        for (int to : g[v]) {
            dp[to] += dp[v];
        }
    }

    cout << dp[6] << '\n';
}

В этом примере программа выведет 3.

---

Если ответы большие: модуль

В задачах число путей очень быстро растёт. Поэтому обычно считают ответ по модулю, например 10^9 + 7.

Тогда переход превращается в:

dp[to] = (dp[to] + dp[v]) % MOD;

Полная версия:

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    vector<int> indeg(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        indeg[b]++;
    }

    int s = 1, t = n;

    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) q.push(v);
    }

    vector<int> topo;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        topo.push_back(v);
        for (int to : g[v]) {
            indeg[to]--;
            if (indeg[to] == 0) q.push(to);
        }
    }

    vector<int> dp(n + 1, 0);
    dp[s] = 1;

    for (int v : topo) {
        for (int to : g[v]) {
            dp[to] += dp[v];
            if (dp[to] >= MOD) dp[to] -= MOD;
        }
    }

    cout << dp[t] << '\n';
}

---

Самый длинный путь в DAG

Это очень важная идея: в DAG можно находить самый длинный путь за линейное время O(n + m).

Это резко отличается от общего ориентированного графа, где задача о самом длинном пути очень сложная.

Динамика

Пусть dp[v] — максимальная длина пути из s в v.

Тогда:

• dp[s] = 0;
• для недостижимых вершин можно считать dp[v] = -INF;
• если есть ребро v -> to, то

dp[to] = max(dp[to], dp[v] + 1)

Если длины рёбер не единичные, а равны w, то:

dp[to] = max(dp[to], dp[v] + w)

Код на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> g(n + 1);
    vector<int> indeg(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        indeg[b]++;
    }

    int s, t;
    cin >> s >> t;

    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) q.push(v);
    }

    vector<int> topo;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        topo.push_back(v);
        for (auto [to, w] : g[v]) {
            indeg[to]--;
            if (indeg[to] == 0) q.push(to);
        }
    }

    const long long NEG = -(long long)4e18;
    vector<long long> dp(n + 1, NEG);
    vector<int> par(n + 1, -1);

    dp[s] = 0;

    for (int v : topo) {
        if (dp[v] == NEG) continue;
        for (auto [to, w] : g[v]) {
            if (dp[v] + w > dp[to]) {
                dp[to] = dp[v] + w;
                par[to] = v;
            }
        }
    }

    if (dp[t] == NEG) {
        cout << "NO PATH\n";
        return 0;
    }

    cout << dp[t] << '\n';

    vector<int> path;
    for (int v = t; v != -1; v = par[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());

    for (int v : path) cout << v << ' ';
    cout << '\n';
}

---

Кратчайший путь в DAG

Для DAG кратчайшие пути тоже можно искать динамикой по топологическому порядку.

Это удобно, когда:

• рёбра могут иметь отрицательные веса,
• но циклов в графе нет.

Тогда алгоритм работает корректно, потому что отрицательный цикл просто не может появиться.

Переход

Пусть dp[v] — минимальная стоимость пути из s в v.

Тогда для ребра v -> to веса w:

dp[to] = min(dp[to], dp[v] + w)

Код на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<pair<int,int>>> g(n + 1);
    vector<int> indeg(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        indeg[b]++;
    }

    int s, t;
    cin >> s >> t;

    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (indeg[v] == 0) q.push(v);
    }

    vector<int> topo;
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        topo.push_back(v);
        for (auto [to, w] : g[v]) {
            indeg[to]--;
            if (indeg[to] == 0) q.push(to);
        }
    }

    const long long INF = (long long)4e18;
    vector<long long> dp(n + 1, INF);
    dp[s] = 0;

    for (int v : topo) {
        if (dp[v] == INF) continue;
        for (auto [to, w] : g[v]) {
            dp[to] = min(dp[to], dp[v] + w);
        }
    }

    if (dp[t] == INF) cout << "NO PATH\n";
    else cout << dp[t] << '\n';
}

---

Минимальное и максимальное число рёбер в пути

Иногда весов у рёбер нет, но нужно узнать не стоимость пути, а:

• минимальное число рёбер,
• максимальное число рёбер.

Это та же самая динамика.

Максимум рёбер

dp[to] = max(dp[to], dp[v] + 1)

Минимум рёбер

dp[to] = min(dp[to], dp[v] + 1)

По сути, мы просто меняем смысл массива dp.

Это хороший урок: очень часто всё решение задачи — это удачно придумать, что означает состояние.

---

Какие вершины обязательно входят в любой путь

Это более содержательная идея, которую полезно понимать.

Пусть надо выяснить, входит ли вершина v в любой путь из s в t.

Сделаем два подсчёта:

• ways_from_s[v] — количество путей из s в v;
• ways_to_t[v] — количество путей из v в t.

Тогда число путей из s в t, проходящих через v, равно:

ways_from_s[v] * ways_to_t[v]

Если это число совпадает с общим числом путей из s в t, то вершина v обязательна.

Почему формула верна

Любой путь через v можно однозначно разбить на две части:

• путь из s в v;
• путь из v в t.

Так как граф ацикличен, комбинации этих частей считаются корректно.

На практике тут часто считают значения по модулю нескольких больших простых чисел или используют long long, если ограничения позволяют.

---

Связь с алгоритмом Дейкстры

В книге есть важная идея: после Дейкстры можно построить DAG кратчайших путей.

Что это значит?

Если мы нашли расстояния dist[v] от старта s, то ребро u -> v веса w лежит на каком-то кратчайшем пути тогда и только тогда, когда

dist[u] + w = dist[v]

Если оставить только такие рёбра, получится ориентированный граф кратчайших переходов. В нём расстояния строго растут, а значит, циклов с нулевым или отрицательным суммарным приростом для обычного случая положительных весов не возникает, и по такому графу удобно запускать DP.

Так можно найти, например:

• число кратчайших путей;
• минимальное число рёбер среди кратчайших путей;
• максимальное число рёбер среди кратчайших путей.

---

Пример: число кратчайших путей после Дейкстры

Пусть после Дейкстры мы уже знаем dist.

Тогда делаем такой переход:

• если dist[v] + w == dist[to], то
• dp[to] += dp[v]

Здесь dp[v] — число кратчайших путей до v.

Такой приём очень часто встречается в задачах.

---

Любая динамика — это DAG состояний

Это, пожалуй, самая важная теоретическая мысль всего раздела.

Любую задачу динамического программирования можно представить как ориентированный ацикличный граф состояний:

• вершина — это состояние;
• ребро — допустимый переход;
• значение в вершине вычисляется через значения в предыдущих вершинах.

Пример с монетами

Пусть есть монеты 1, 3, 4, и нужно набрать сумму 6.

Можно построить граф состояний:

• вершины: суммы 0, 1, 2, 3, 4, 5, 6;
• ребро x -> x + c, если можно добавить монету c.

Тогда:

• подсчёт числа способов получить сумму — это подсчёт числа путей из 0 в 6;
• поиск минимального числа монет — это кратчайший путь в этом графе;
• поиск максимального числа монет при дополнительных условиях — другая вариация динамики.

Получается, что DP — это не набор отдельных формул, а единый способ думать о зависимостях между состояниями.

---

Универсальный шаблон DP по DAG

Пусть есть DAG и стартовая вершина s.

Шаблон для подсчёта количества путей

dp[s] = 1
остальные dp = 0

идём по вершинам в топологическом порядке:
    для каждого ребра v -> to:
        dp[to] += dp[v]

Шаблон для максимума

dp[s] = 0
остальные dp = -INF

идём по вершинам в топологическом порядке:
    для каждого ребра v -> to:
        dp[to] = max(dp[to], dp[v] + cost)

Шаблон для минимума

dp[s] = 0
остальные dp = INF

идём по вершинам в топологическом порядке:
    для каждого ребра v -> to:
        dp[to] = min(dp[to], dp[v] + cost)

Это три наиболее часто используемых формы.

---

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

1. Забыли, что граф должен быть DAG

Если есть цикл, простой проход по топологическому порядку невозможен.

2. Неправильно задали базу

Например, для подсчёта путей нужно поставить dp[s] = 1, а не 0.

3. Переполнение

Количество путей может быть огромным. Часто нужен модуль.

4. Не отделили недостижимые вершины

Для задач на минимум и максимум обязательно используйте INF и -INF, иначе переходы могут стать некорректными.

5. Смешали направление переходов

Можно считать либо по входящим рёбрам, либо по исходящим. Оба способа нормальны, но надо выбрать один и не путаться.

---

Асимптотика

Если топологический порядок уже построен, то большинство таких DP работают за O(n + m):

• каждая вершина обрабатывается один раз;
• каждое ребро рассматривается один раз.

Если топологическую сортировку тоже строить, итоговая сложность всё равно останется O(n + m).

Это очень быстро и делает DAG одним из самых удобных видов графов для задач.

---

Небольшое упражнение для понимания

Пусть задан DAG и вершины s и t.

Попробуйте для одной и той же структуры графа написать три решения:

1. число путей из s в t;
2. длина самого длинного пути из s в t;
3. минимальное количество рёбер среди всех путей из s в t.

Вы заметите, что отличается почти только смысл массива dp и операция в переходе.

Это и есть главный навык в динамике: увидеть одно и то же устройство решения в разных задачах.

---

Вывод

Динамическое программирование на ориентированных ацикличных графах — это очень важная техника.

Нужно запомнить три ключевые идеи:

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

Если в задаче зависимости между состояниями не образуют циклов, почти всегда стоит проверить, не скрывается ли там DP по DAG.

---

Короткая памятка

• DAG + топологическая сортировка = почти готовая основа для DP.
• dp[v] должен иметь чёткий смысл.
• Переходы идут по рёбрам.
• Порядок вычисления — топологический.
• Для подсчёта путей обычно база dp[s] = 1.
• Для минимума и максимума нужны INF и -INF.
• Сложность обычно O(n + m).