45 · 回顾八：图论

暴力 O(N(N+M)) 必 TLE。突破口是：A(v) 一定是 v 能到达的点里编号最大的那个，而「能到达」在反图上就是「被到达」。

把每条边反向：原图 u → v 存成反图 v → u。这样从 i 在反图上能走到的每个 x，都满足「原图上 x 能走到 i」，于是 A(x) ≥ i。

从 N 往 1 枚举 i。若 ans[i] 还没被赋值，就从 i 在反图上 BFS，把沿途所有未赋值的点都标成 i。

正确性：设 x 被标成 i。① 反图上 i 到 x 有路 → 原图 x 到 i 有路 → A(x) ≥ i；② 任何 j > i 都在更早的轮次处理过，若 x 能到 j，反图上 j 就能到 x，x 早被标成 ≥ j 的值，矛盾。所以 A(x) 恰好是 i。

复杂度：每个点只被赋值一次、入队一次，每条反边最多扫一次，总 O(N+M)，N = M = 10⁵ 时约 2×10⁵ 次操作。

细节：i 必须先令 ans[i] = i 再入队，否则没有出边的点会输出 0。

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

const int MAXN = 100005;
int n, m;
vector<int> rg[MAXN];        // 反图：原边 u -> v 在这里存成 v -> u
int ans[MAXN];               // ans[v]：v 能到达的最大编号；0 表示还没定

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        rg[v].push_back(u);             // 唯一改动：反向建边
    }

    for (int i = n; i >= 1; --i) {      // 从大到小扫：先被覆盖的答案就是最大的
        if (ans[i]) continue;           // 更大的点已经把它定过了
        ans[i] = i;                     // 自己一定能到达自己
        queue<int> q;
        q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : rg[u]) {
                if (ans[v]) continue;
                ans[v] = i;             // 反图 i 能到 v，等价于原图 v 能到 i
                q.push(v);
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i > 1) putchar(' ');
        printf("%d", ans[i]);
    }
    putchar('\n');
    return 0;
}

Dijkstra 把点分成「最短路已确定」和「未确定」两组。每轮从未确定集合里取 dist 最小的点 u，把 dist[u] 定为最终答案，再用 u 松弛它的所有出边。

为什么取最小就一定定案：任何到 u 的更短路径必然先经过某个未确定点 x，而 dist[x] ≥ dist[u]；边权非负，绕过去只会更长。这与「u 是最小」矛盾。

朴素实现每轮 O(n) 找最小，总 O(n²)，n = 10⁵ 时 10¹⁰，必 TLE。

把 (dist, 编号) 塞进小根堆，堆顶就是当前最小：每个点松弛成功就入堆一次，取出时若 d > dist[u] 说明是过期版本，直接丢弃。

复杂度 O((n+m) log n)。m = 2×10⁵ 时堆操作不超过 4×10⁵ 次，每次 log(4×10⁵) ≈ 19，总共约 8×10⁶ 次比较，1 秒内稳过。

类型：Σwᵢ ≤ 10⁹ 意味着最短路也在 10⁹ 量级，int 勉强够；但 d + w 在 INF 上做加法时用 int 容易溢出，一律 long long，不必再算边界。

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

const int MAXN = 100005;
typedef long long ll;
typedef pair<ll, int> pli;              // (距离, 编号)

int n, m, s;
vector<pair<int,int>> g[MAXN];          // (终点, 边权)
ll dist[MAXN];

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});         // 有向边，只加一次
    }

    const ll INF = LLONG_MAX / 2;       // 足够大且加 w 不会溢出
    fill(dist, dist + n + 1, INF);
    dist[s] = 0;

    priority_queue<pli, vector<pli>, greater<pli>> pq;   // 小根堆
    pq.push({0, s});
    while (!pq.empty()) {
        pli cur = pq.top(); pq.pop();
        ll d = cur.first;
        int u = cur.second;
        if (d > dist[u]) continue;      // 过期版本：u 后来被更短的路径更新过
        for (auto &e : g[u]) {
            int v = e.first, w = e.second;
            if (dist[v] > d + w) {      // 松弛成功才入堆
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 1; i <= n; ++i) {
        if (i > 1) putchar(' ');
        printf("%lld", dist[i]);
    }
    putchar('\n');
    return 0;
}

总时间 = Σ( 1→i 的最短路 + i→1 的最短路 )，i = 2…n。两项分别算。

第一项：以 1 为源，在原图上跑一次 Dijkstra。

第二项：i → 1 的起点各不相同，但把每条边反向之后，「i → 1」就变成了「1 → i」。所以建一张反图，再从 1 跑一次 Dijkstra。

为什么等价：原图上一条 i → a → b → 1 的路径，把每条边反向就得到反图上 1 → b → a → i 的路径，边权逐一对应，长度完全一样，且这是双射。

复杂度：两次 Dijkstra，O((n+m) log n)。n = 10³、m = 10⁵ 时约 10⁵×10 次操作。若对每个 i 单独跑一次，是 10³ × 10⁵ = 10⁸ 量级以上，1 秒很难过。

类型：单条最短路 ≤ (n−1)×10⁴ ≈ 10⁷，int 够；但 n−1 条加起来到 10¹⁰，累加答案时必须 long long。样例：正向和 28，反向和 55，总共 83。

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

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;         // 1.06e9，比任何真实最短路都大，加 w 也不溢出
int n, m;
vector<pair<int,int>> g[MAXN], rg[MAXN];   // (终点, 权值)；g 正图，rg 反图
int d1[MAXN], d2[MAXN];

// 从 1 出发，在 gr 这张图上跑 Dijkstra，结果写进 d
void dijkstra(vector<pair<int,int>> gr[], int d[]) {
    fill(d, d + n + 1, INF);
    d[1] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({0, 1});
    while (!pq.empty()) {
        auto [du, u] = pq.top(); pq.pop();
        if (du > d[u]) continue;                 // 过期版本
        for (auto [v, w] : gr[u])
            if (d[v] > du + w) {
                d[v] = du + w;
                pq.push({d[v], v});
            }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});                  // 送出去：u -> v
        rg[v].push_back({u, w});                 // 反图：用来算「从 i 回 1」
    }

    dijkstra(g, d1);                             // d1[i] = 1 -> i
    dijkstra(rg, d2);                            // d2[i] = i -> 1

    long long ans = 0;                           // 10³ 条 10⁷ 的路，必须 long long
    for (int i = 2; i <= n; ++i) ans += (long long)d1[i] + d2[i];
    cout << ans << "\n";
    return 0;
}

Kruskal：所有边按权值升序排序，依次尝试加入。若两端已经在同一连通块里就跳过（加入会成环），否则选中这条边并把两个连通块合并。选满 n−1 条即结束。

正确性（割性质）：设 e 是当前剩下的边里权最小的，且两端分属不同连通块。任何一棵生成树都必须有某条边跨过这个割；把那条边换成 e，总权不会变大。所以 e 一定可以出现在某棵最小生成树中，删去这个子问题后归纳成立。

并查集负责「是否连通」与「合并」：路径压缩后单次接近 O(1)。

复杂度由排序决定：O(m log m)。m = 2×10⁵ 时约 3.6×10⁶ 次比较，并查集部分几乎不耗时。

判不连通：最后选中的边数 cnt < n−1，说明有的点始终连不进来，输出 orz。

边界：n = 1 时不需要任何边，cnt = 0 = n−1，输出 0；题目数据里 n ≥ 1。

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

const int MAXN = 5005, MAXM = 200005;
int n, m;
struct Edge { int u, v, w; } e[MAXM];
int fa[MAXN];

int find(int x) {                       // 路径压缩，迭代写法
    while (fa[x] != x) {
        fa[x] = fa[fa[x]];
        x = fa[x];
    }
    return x;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);

    sort(e, e + m, [](const Edge &a, const Edge &b) { return a.w < b.w; });

    for (int i = 1; i <= n; ++i) fa[i] = i;   // 每个点自成一个集合，不能省

    int cnt = 0;
    long long sum = 0;
    for (int i = 0; i < m && cnt < n - 1; ++i) {
        int a = find(e[i].u), b = find(e[i].v);
        if (a == b) continue;             // 已连通：加入就成环
        fa[a] = b;                        // 合并两个根
        sum += e[i].w;
        ++cnt;
    }

    if (cnt == n - 1) printf("%lld\n", sum);
    else puts("orz");                     // 不连通，按题目要求输出
    return 0;
}

建图：B 吃 A，就加有向边 A → B。于是「生产者」= 入度为 0 的点（它不吃任何别的生物），「顶级消费者」= 出度为 0 的点（没有生物吃它）。食物链 = 从入度 0 走到出度 0 的一条路径。

状态：dp[u] = 以 u 结尾的食物链条数。初值：入度为 0 的点 dp = 1，它自己就是一条链的开头。

转移：按拓扑序处理，每遇到边 u → v，就 dp[v] += dp[u]，随时对 80112002 取模。

答案：Σ dp[u]，只累加出度为 0 的点——链必须在顶级消费者结束，中途的点不能计入。

为什么拓扑序就够：处理到 u 时，所有能到达 u 的点都已经把贡献加进了 dp[u]，不会漏；u 只会被处理一次，不会重。

复杂度 O(n+m)。m = 5×10⁵、时限 1 秒，读入必须用 scanf；dp 的加法在 int 内完成（模数 8×10⁷，两数相加不超过 1.7×10⁸）。

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

const int MAXN = 5005;
const int MOD = 80112002;
int n, m;
vector<int> g[MAXN];
int indeg[MAXN], outdeg[MAXN];      // 入度 = 它吃几种；出度 = 几种吃它
int dp[MAXN];                       // dp[u]：以 u 结尾的食物链条数

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);      // B 吃 A
        g[a].push_back(b);          // 链的方向：被吃者 -> 捕食者
        ++indeg[b];
        ++outdeg[a];
    }

    queue<int> q;
    for (int i = 1; i <= n; ++i)
        if (indeg[i] == 0) {        // 生产者：链的起点
            dp[i] = 1;
            q.push(i);
        }

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            dp[v] = (dp[v] + dp[u]) % MOD;   // 所有以 u 结尾的链都能延长到 v
            if (--indeg[v] == 0) q.push(v);  // v 的全部前驱都处理完了
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
        if (outdeg[i] == 0)                  // 顶级消费者：链的终点
            ans = (ans + dp[i]) % MOD;
    printf("%d\n", ans);
    return 0;
}