营养平衡物种

彭子昂 @ 2026-5-8 16:50:30

以下是题解与C++代码实现。

题解思路

缩点：用Tarjan求强连通分量（SCC），将原图缩成DAG。每个SCC内部点互相可达，因此同一个SCC中所有原始节点的 $out$ 、 $in$ 值相同（因为SCC内点能到达的外部节点和能到达它的外部节点一致）。记SCC个数为 $N$ ，每个SCC的权值 $size[u]$ 为原始节点数。
最小路径覆盖：在DAG上，最大反链大小 $\le k$ ，由Dilworth定理，最小路径覆盖数 $=$ 最大反链大小 $\le k$ 。我们通过二分图最大匹配（Hopcroft–Karp算法）求最小路径覆盖，得到不超过 $k$ 条路径。每条路径是DAG上的一条有向路径（节点序列），且路径内部节点两两可达。
DP计算可达数量：
- 对每条路径 $i$ ，记录其节点顺序（拓扑序）。定义 $low_i[u]$ 为从 $u$ 出发能到达该路径上的最小索引（即最早位置）。通过逆拓扑序DP更新：初始化若 $u$ 在路径 $i$ 上，则 $low_i[u]$ 为其索引，否则为 $+\infty$ ；对每条边 $(u \to v)$ ，令 $low_i[u] = \min(low_i[u], low_i[v])$ 。最后， $u$ 能到达该路径上的节点数为 $\max(0, len_i - low_i[u] + 1)$ （若 $low_i[u] > len_i$ 则为0）。
- $out(u) = \sum_i (len_i - low_i[u] + 1) - 1$ （减去自身）。
- 对称地，定义 $high_i[u]$ 为能到达 $u$ 的节点在该路径上的最大索引。通过正向拓扑序DP：若 $u$ 在路径上则 $high_i[u]$ 为其索引，否则为0；对边 $(u \to v)$ ， $high_i[v] = \max(high_i[v], high_i[u])$ 。则 $in(u) = \sum_i high_i[u] - 1$ 。
- 平衡值 $f(u) = |out(u) - in(u)|$ 。
还原答案： $f$ 值最小的SCC即营养平衡物种所在的SCC，输出这些SCC中包含的所有原始节点编号（升序）。

复杂度分析

Tarjan： $O(n+m)$
Hopcroft–Karp： $O(m\sqrt{N})$ ， $N\le 2\times10^5,m\le4\times10^5$ ，可接受
DP： $O(k(N+m))$ ， $k\le16$
总时间约 $2\times10^8$ 量级，优化后可在3秒内运行。

C++代码

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

typedef long long ll;
const int INF = 1e9;

// ---------- Hopcroft–Karp 二分图最大匹配 ----------
struct HopcroftKarp {
    int n, m; // 左部大小, 右部大小
    vector<vector<int>> adj;
    vector<int> matchL, matchR, dist;
    HopcroftKarp(int n, int m) : n(n), m(m), adj(n), matchL(n, -1), matchR(m, -1) {}
    void addEdge(int u, int v) { adj[u].push_back(v); }
    bool bfs() {
        queue<int> q;
        dist.assign(n, -1);
        for (int u = 0; u < n; u++) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            }
        }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (matchR[v] != -1 && dist[matchR[v]] == -1) {
                    dist[matchR[v]] = dist[u] + 1;
                    q.push(matchR[v]);
                } else if (matchR[v] == -1) {
                    found = true;
                }
            }
        }
        return found;
    }
    bool dfs(int u) {
        for (int v : adj[u]) {
            if (matchR[v] == -1 || (dist[matchR[v]] == dist[u] + 1 && dfs(matchR[v]))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = -1;
        return false;
    }
    int maxMatching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < n; u++) {
                if (matchL[u] == -1 && dfs(u)) {
                    matching++;
                }
            }
        }
        return matching;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
    }

    // ---------- Tarjan 缩点 ----------
    vector<int> dfn(n, -1), low(n), stk, scc_id(n, -1);
    vector<bool> in_stk(n, false);
    int timer = 0, scc_cnt = 0;
    function<void(int)> tarjan = [&](int u) {
        dfn[u] = low[u] = timer++;
        stk.push_back(u);
        in_stk[u] = true;
        for (int v : g[u]) {
            if (dfn[v] == -1) {
                tarjan(v);
                low[u] = min(low[u], low[v]);
            } else if (in_stk[v]) {
                low[u] = min(low[u], dfn[v]);
            }
        }
        if (dfn[u] == low[u]) {
            int v;
            do {
                v = stk.back(); stk.pop_back();
                in_stk[v] = false;
                scc_id[v] = scc_cnt;
            } while (v != u);
            scc_cnt++;
        }
    };
    for (int i = 0; i < n; i++) {
        if (dfn[i] == -1) tarjan(i);
    }

    // 构建 DAG (SCC 图)
    vector<int> scc_size(scc_cnt, 0);
    for (int i = 0; i < n; i++) {
        scc_size[scc_id[i]]++;
    }
    vector<set<int>> dag(scc_cnt);
    for (int u = 0; u < n; u++) {
        for (int v : g[u]) {
            int su = scc_id[u], sv = scc_id[v];
            if (su != sv) {
                dag[su].insert(sv);
            }
        }
    }
    // 转成邻接表
    vector<vector<int>> dag_adj(scc_cnt);
    for (int u = 0; u < scc_cnt; u++) {
        dag_adj[u].assign(dag[u].begin(), dag[u].end());
    }

    // ---------- 最小路径覆盖 (Hopcroft–Karp) ----------
    int N = scc_cnt;
    HopcroftKarp hk(N, N);
    for (int u = 0; u < N; u++) {
        for (int v : dag_adj[u]) {
            hk.addEdge(u, v);
        }
    }
    int match_size = hk.maxMatching();
    // 路径数 = N - match_size
    // 还原路径
    vector<int> matchL = hk.matchL, matchR = hk.matchR;
    vector<bool> vis(N, false);
    vector<tuple<int,int,int>> path_info; // (path_id, position, node)
    vector<int> path_id(N, -1), pos_in_path(N, -1);
    int cur_path = 0;
    // 处理作为起点的节点 (左未匹配)
    for (int u = 0; u < N; u++) {
        if (matchL[u] != -1) continue; // 不是起点
        // 开始构造路径
        vector<int> path;
        int x = u;
        while (x != -1) {
            path.push_back(x);
            vis[x] = true;
            int y = matchL[x]; // 右节点
            if (y == -1) break;
            x = y; // 下一个左节点就是 y
        }
        // 记录路径信息
        int len = path.size();
        for (int i = 0; i < len; i++) {
            int node = path[i];
            path_id[node] = cur_path;
            pos_in_path[node] = i; // 0-index
        }
        cur_path++;
    }
    // 处理孤立节点 (没有被任何边匹配的节点，既没有左匹配也没有右匹配)
    for (int u = 0; u < N; u++) {
        if (!vis[u]) {
            path_id[u] = cur_path;
            pos_in_path[u] = 0;
            cur_path++;
        }
    }
    int P = cur_path; // 路径数
    vector<int> path_len(P, 0);
    for (int u = 0; u < N; u++) {
        int pid = path_id[u];
        path_len[pid] = max(path_len[pid], pos_in_path[u] + 1);
    }

    // ---------- DP 计算 low (能到达的最小位置) ----------
    // 拓扑序 (DAG)
    vector<int> indeg(N, 0);
    for (int u = 0; u < N; u++) {
        for (int v : dag_adj[u]) indeg[v]++;
    }
    queue<int> q;
    for (int i = 0; i < N; i++) if (indeg[i] == 0) q.push(i);
    vector<int> topo;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int v : dag_adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) q.push(v);
        }
    }
    // 逆拓扑序
    vector<int> rev_topo = topo;
    reverse(rev_topo.begin(), rev_topo.end());

    vector<vector<int>> low(P, vector<int>(N, INF));
    for (int u = 0; u < N; u++) {
        int pid = path_id[u];
        low[pid][u] = pos_in_path[u];
    }
    // 逆序 dp
    for (int u : rev_topo) {
        for (int v : dag_adj[u]) {
            for (int pid = 0; pid < P; pid++) {
                low[pid][u] = min(low[pid][u], low[pid][v]);
            }
        }
    }
    // 计算 out
    vector<ll> out_sum(N, 0);
    for (int u = 0; u < N; u++) {
        ll tot = 0;
        for (int pid = 0; pid < P; pid++) {
            int l = low[pid][u];
            if (l <= path_len[pid]-1) {
                tot += path_len[pid] - l;
            }
        }
        tot--; // 减去自身
        out_sum[u] = tot;
    }

    // ---------- DP 计算 high (能到达的最大位置) ----------
    vector<vector<int>> high(P, vector<int>(N, -1));
    for (int u = 0; u < N; u++) {
        int pid = path_id[u];
        high[pid][u] = pos_in_path[u];
    }
    // 正序 dp
    for (int u : topo) {
        for (int v : dag_adj[u]) {
            for (int pid = 0; pid < P; pid++) {
                high[pid][v] = max(high[pid][v], high[pid][u]);
            }
        }
    }
    vector<ll> in_sum(N, 0);
    for (int u = 0; u < N; u++) {
        ll tot = 0;
        for (int pid = 0; pid < P; pid++) {
            int h = high[pid][u];
            if (h >= 0) {
                tot += h + 1; // 从 0 到 h 共 h+1 个节点
            }
        }
        tot--; // 减去自身
        in_sum[u] = tot;
    }

    // 计算每个 SCC 的 f 值
    vector<ll> f_scc(N, 0);
    ll min_f = LLONG_MAX;
    for (int u = 0; u < N; u++) {
        f_scc[u] = abs(out_sum[u] - in_sum[u]);
        min_f = min(min_f, f_scc[u]);
    }

    // 找出所有原始节点中属于 f_scc == min_f 的 SCC 的节点
    vector<int> ans;
    for (int i = 0; i < n; i++) {
        int sid = scc_id[i];
        if (f_scc[sid] == min_f) {
            ans.push_back(i+1);
        }
    }
    sort(ans.begin(), ans.end());
    for (size_t i = 0; i < ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';

    return 0;
}

ID

7018

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

彭子昂

1 条题解

题解思路

复杂度分析

C++代码

信息

还没有账户？

登录