采蘑菇

GitHub跳转原题关系图返回列表

通过 Tarjan 缩点将强连通分量内的边转化为完全采摘的点权，跨分量的边化为单次通行的有向边，再在 DAG 上利用拓扑排序求最长路。

OJ: luogu

题目 ID: P2656

难度:普及+/提高-

标签:图论Tarjan强连通分量拓扑排序动态规划

创建: 2026-10-23 23:04

更新: 2026-10-23 23:27

目录

  1. 形式化题目
  2. 暴力解法
    1. 思路
    2. 代码
    3. 复杂度
    4. 瓶颈
  3. 正解
    1. 思路
    2. 代码
    3. 复杂度
  4. 总结

形式化题目

给定一个包含 NN 个顶点、MM 条有向边的有向图 G=(V,E)G = (V, E) 以及出发起点 SS。 每条有向边具有初始边权 ww 以及衰减系数 k∈[0,0.8]k \in [0, 0.8]（最多一位小数）。 每当沿有向边通行一次：

  1. 获得当前边上所有的蘑菇收益 ww；
  2. 该边的蘑菇数更新为 ⌊w×k⌋\lfloor w \times k \rfloor。

求从起点 SS 出发沿图上有向路径行走（允许重复经过顶点和边），所能收集的最大蘑菇总数。

暴力解法

思路

针对小规模数据，可以直接采用带回溯的深度优先搜索（DFS）在图上模拟游走。 每次尝试走一条出边，累加采摘到的蘑菇，将该边当前的蘑菇数衰减，并递归到下一节点。 因为 k≤0.8<1k \le 0.8 < 1，边权每次至少按比例衰减，经过有限次后必然归零。通过限制连续未获得收益的步数或最大搜索深度来进行剪枝回溯。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:20
 * update_at: 2026-10-23 23:20
 */
// brute.cpp：小数据暴力解法
// 针对小规模图，利用带剪枝的深度优先搜索在图上模拟采蘑菇过程。
// 只适用于点数极小（N <= 5）且边数极少的情况，步数上限设为 25。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 10;
const int MAXM = 30;

int n, m, s;

struct Edge {
    int u, v;
    ll w;
    int k;
};

Edge edges[MAXM];
vector<int> g[MAXN];

ll ans = 0;

void dfs(int u, ll sum, int step, int zero_gain_steps) {
    if (sum > ans) {
        ans = sum;
    }
    if (step >= 25) return;
    if (zero_gain_steps >= 4) return;

    for (int e_idx : g[u]) {
        int v = edges[e_idx].v;
        ll old_w = edges[e_idx].w;
        ll gain = old_w;
        edges[e_idx].w = (old_w * edges[e_idx].k) / 10;

        dfs(v, sum + gain, step + 1, (gain == 0 ? zero_gain_steps + 1 : 0));

        edges[e_idx].w = old_w;
    }
}

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

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        ll w;
        double coef;
        cin >> u >> v >> w >> coef;
        edges[i] = {u, v, w, (int)round(coef * 10)};
        g[u].push_back(i);
    }
    cin >> s;

    dfs(s, 0, 0, 0);

    cout << ans << "\n";
    return 0;
}

复杂度

  • 时间复杂度：搜索树的分支因子取决于顶点的出度，状态空间随搜索步数呈指数级爆炸，最坏情况下为 O(dL)O(d^L)（其中 dd 为平均出度，LL 为搜索截断步数）。
  • 空间复杂度：递归栈及图存储占用 O(N+M)O(N + M) 空间。

瓶颈

暴力的核心瓶颈在于：由于有向图中存在环路，且走同一条边多次会有连续衰减收益，搜索树深度大、状态数量庞大，无法处理 N≤8×104,M≤2×105N \le 8\times 10^4, M \le 2\times 10^5 的全局图。

正解

思路

我们可以抓住图的结构特征与收益规律：

  1. 单条边的全收益： 若一条初始蘑菇数为 ww、衰减系数为 kk 的边被反复经过，其最大可能获得的收益是确定的：

    gain(w,k)=∑t=0∞wt(w0=w,wt+1=⌊wt×k⌋) \text{gain}(w, k) = \sum_{t=0}^{\infty} w_t \quad (w_0 = w, w_{t+1} = \lfloor w_t \times k \rfloor)
    因为 k≤0.8k \le 0.8，衰减极快，直接循环数次即可求得该和式。

  2. 强连通分量（SCC）内的边： 在同一个强连通分量内，任意两点双向可达。因此只要进入了某个强连通分量，我们总可以通过在环路上往返走动，将该分量内部所有边的蘑菇完全采光（全部采到 0），并且最后停留在该分量内的任意一个出口节点。 因此，我们可以用 Tarjan 算法 进行缩点，将每个强连通分量缩成一个“超级点”，其点权等于该分量内部所有边的全收益之和 ∑gain(w,k)\sum \text{gain}(w, k)。

  3. 跨强连通分量的边： 对于连接两个不同强连通分量 u→vu \to v 的边，由于缩点后生成的图是有向无环图（DAG），一旦穿过此边到达后续分量，就绝对不可能再返回原分量。因此，跨分量的边至多只能被经过一次，其贡献为且仅为其初始权值 ww。

  4. DAG 上的最长路： 缩点建图后，我们在 DAG 上求以包含起点 SS 的超级点为起点的最长路。 设 dist[i]dist[i] 表示从起点超级点出发到达超级点 ii 所能获得的最大蘑菇数：

    • 初始化：dist[SCC(S)]=点权[SCC(S)]dist[SCC(S)] = \text{点权}[SCC(S)]，其余节点设为不可达（−1-1）；
    • 按拓扑排序的顺序进行状态转移：
      dist[v]=max⁡(dist[v],dist[u]+w(u,v)+点权[v]) dist[v] = \max(dist[v], dist[u] + w_{(u, v)} + \text{点权}[v])
    • 最终全局最大采蘑菇数即为 max⁡idist[i]\max_{i} dist[i]。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:20
 * update_at: 2026-10-23 23:20
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 80005;
const int MAXM = 200005;

// 原图与缩点后图的链式前向星
int head[MAXN], edge_cnt;
struct Edge {
    int to;
    int next;
    ll w;
    int coef; // 衰减系数 * 10
} edges[MAXM];

void add_edge(int u, int v, ll w, int coef) {
    edge_cnt++;
    edges[edge_cnt].to = v;
    edges[edge_cnt].next = head[u];
    edges[edge_cnt].w = w;
    edges[edge_cnt].coef = coef;
    head[u] = edge_cnt;
}

// 原始输入的边，供缩点后重构图使用
struct RawEdge {
    int u, v;
    ll w;
    int coef;
} raw_edges[MAXM];

// Tarjan 缩点相关变量
int dfn[MAXN], low[MAXN], timer;
int stk[MAXN], top;
bool in_stack[MAXN];
int scc[MAXN], scc_cnt;
ll scc_weight[MAXN]; // 每个强连通分量内部所有边的全收益之和

// 计算一条边反复经过直至为 0 的总蘑菇数
ll calc_all_gain(ll w, int coef) {
    ll sum = 0;
    while (w > 0) {
        sum += w;
        w = (w * coef) / 10;
    }
    return sum;
}

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;
    in_stack[u] = true;

    for (int e = head[u]; e; e = edges[e].next) {
        int v = edges[e].to;
        if (!dfn[v]) {
            tarjan(v);
            if (low[v] < low[u]) low[u] = low[v];
        } else if (in_stack[v]) {
            if (dfn[v] < low[u]) low[u] = dfn[v];
        }
    }

    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int node = stk[top--];
            in_stack[node] = false;
            scc[node] = scc_cnt;
            if (node == u) break;
        }
    }
}

// 缩点后 DAG 的链式前向星
int dag_head[MAXN], dag_edge_cnt;
struct DagEdge {
    int to;
    int next;
    ll w;
} dag_edges[MAXM];

int in_degree[MAXN];

void add_dag_edge(int u, int v, ll w) {
    dag_edge_cnt++;
    dag_edges[dag_edge_cnt].to = v;
    dag_edges[dag_edge_cnt].next = dag_head[u];
    dag_edges[dag_edge_cnt].w = w;
    dag_head[u] = dag_edge_cnt;
    in_degree[v]++;
}

// DAG 拓扑排序求最长路
ll dist[MAXN];
int q[MAXN];

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

    int n, m;
    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= m; ++i) {
        int u, v;
        ll w;
        double c;
        cin >> u >> v >> w >> c;
        int coef = (int)round(c * 10);
        raw_edges[i] = {u, v, w, coef};
        add_edge(u, v, w, coef);
    }

    int start_node;
    cin >> start_node;

    // 运行 Tarjan 缩点
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // 统计强连通分量内部边的贡献，并建立 DAG 边
    for (int i = 1; i <= m; ++i) {
        int u = raw_edges[i].u;
        int v = raw_edges[i].v;
        int su = scc[u];
        int sv = scc[v];
        if (su == sv) {
            scc_weight[su] += calc_all_gain(raw_edges[i].w, raw_edges[i].coef);
        } else {
            // 跨分量的单向边，只能采一次（因为 DAG 无法走回路）
            add_dag_edge(su, sv, raw_edges[i].w);
        }
    }

    // 在 DAG 上求从 scc[start_node] 出发的最长路
    int start_scc = scc[start_node];
    for (int i = 1; i <= scc_cnt; ++i) {
        dist[i] = -1; // -1 表示从起点不可达
    }
    dist[start_scc] = scc_weight[start_scc];

    // 拓扑排序
    int front = 0, rear = 0;
    for (int i = 1; i <= scc_cnt; ++i) {
        if (in_degree[i] == 0) {
            q[rear++] = i;
        }
    }

    ll ans = dist[start_scc];

    while (front < rear) {
        int u = q[front++];
        for (int e = dag_head[u]; e; e = dag_edges[e].next) {
            int v = dag_edges[e].to;
            if (dist[u] != -1) {
                ll cand = dist[u] + dag_edges[e].w + scc_weight[v];
                if (cand > dist[v]) {
                    dist[v] = cand;
                }
            }
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q[rear++] = v;
            }
        }
    }

    for (int i = 1; i <= scc_cnt; ++i) {
        if (dist[i] > ans) {
            ans = dist[i];
        }
    }

    cout << ans << "\n";

    return 0;
}

复杂度

  • 时间复杂度：
    • Tarjan 缩点遍历原图点和边，时间复杂度为 O(N+M)O(N + M)；
    • 预处理每条边的全收益，由于每次衰减至少减少 20%20\%，每条边最多计算 log⁡1/0.8w≈30\log_{1/0.8} w \approx 30 次，复杂度为 O(Mlog⁡w)O(M \log w)；
    • 缩点后在新图上拓扑排序和动态规划，耗时为 O(N′+M′)=O(N+M)O(N' + M') = O(N + M)；
    • 总体时间复杂度为 O(N+Mlog⁡w)O(N + M \log w)，在 N=8×104,M=2×105N = 8 \times 10^4, M = 2 \times 10^5 规模下只需几十毫秒，运行极为充裕。
  • 空间复杂度：
    • 原图和缩点后的 DAG 均使用全局静态链式前向星存储，额外维护 Tarjan 栈与拓扑队列；
    • 总体空间复杂度为 O(N+M)O(N + M)，占用内存约 15MB 左右，远在空间限制内。

总结

本题的关键在于利用强连通分量内部可无限循环的特点，将环内的无穷衰减收益一次性全部结算为超级点的静态点权；再利用**缩点后图无环（DAG）**的性质，将环外边的遍历次数锁定为至多一次，从而将复杂的有环图最值路径问题转化为了经典的 DAG 最长路模型。