[Leaf] P2656 采蘑菇

p2656-采蘑菇---洛谷">P2656 采蘑菇 - 洛谷

1. 题面梗概

中译中：给一张有向图，边权有初始值 $w$ 和恢复系数 $c$。每次经过边，采走当前所有蘑菇，随后边权变为 $\lfloor w \cdot c \rfloor$。求从起点 $S$ 出发能采到的最大蘑菇数。

$N \le 8 \times 10^4, M \le 2 \times 10^5, c \le 0.8$

2. 逻辑推导

注意到是个有向图，如果某一组点构成了环（强连通分量），我们就可以沿着环不断绕圈。由于 $c < 1$，所以边权会衰减到 $0$，这就意味着，只要进入了某个 SCC，所有的边收益之和都可以纳入囊中。

然后接下来的思路就很简单，显然了。

Tarjan 缩点：找出所有的强联通分量。

SCC 收益统计：计算边权的收敛收益和。

DAG 最长路：拓扑排序 + DP。

3. 代码实现

▶

AcCode

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

const int maxn = 8e4 + 5;

struct Edge { int v, w, coe; };
vector< Edge > adj[maxn];
int dfn[maxn], low[maxn], timer;
int scc[maxn], scc_cnt;
ll scc_val[maxn];
bool in_stk[maxn];
int indeg[maxn];
stack< int > stk;
int n, m, s;

ll calc( int w, int coe )
{
    ll sum = 0;
    while( w > 0 ) {
        sum += w;
        w = w * coe / 10;
    }
    return sum;
}

void tarjan( int u )
{
    dfn[u] = low[u] = ++ timer;
    stk.push( u ); in_stk[u] = 1;
    
    for( auto [v, w, coe] : adj[u] )
    {
        if( !dfn[v] )
        {
            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] )
    {
        scc_cnt ++;
        int v;
        do {
            v = stk.top( ); stk.pop( );
            in_stk[v] = 0;
            scc[v] = scc_cnt;
        } while( v != u );
    }
}

struct Edge2 { int v; ll w; };
vector< Edge2 > dag[maxn];
ll dist[maxn];

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;

    for( int i = 1; i <= m; ++ i )
    {
        int u, v, w; double _c;
        cin >> u >> v >> w >> _c;
        int c = (int)( _c * 10 );
        adj[u].push_back({ v, w, c });
    }

    cin >> s;

    for( int i = 1; i <= n; ++ i )
    {
        if( !dfn[i] ) tarjan( i );
    }

    for( int u = 1; u <= n; ++ u )
    {
        for( auto [v, w, coe] : adj[u] )
        {
            if( scc[u] == scc[v] )
            {
                scc_val[scc[u]] += calc( w, coe );
            }
            else
            {
                dag[scc[u]].push_back({ scc[v], (ll)w });
                indeg[scc[v]] ++;
            }
        }
    }

    for( int i = 1; i <= scc_cnt; ++ i ) dist[i] = -1;
    dist[scc[s]] = scc_val[scc[s]];

    queue< int > q;
    for( int i = 1; i <= scc_cnt; ++ i )
        if( indeg[i] == 0 ) q.push( i );

    ll ans = 0;
    while( !q.empty( ) )
    {
        int u = q.front( ); q.pop( );
        ans = max( ans, dist[u] );

        for( auto [v, w] : dag[u] )
        {
            if( dist[u] != -1 ) dist[v] = max( dist[v], dist[u] + w + scc_val[v] );
            if( -- indeg[v] == 0 ) q.push( v );
        }
    }
    
    cout << ans << '\n';
    return 0;
}

4. 复盘

• 复杂度分析：$O( N + M )$。

• 碎碎念：DAG 缩点后的 拓扑+DP 求 最长路。

• 关联笔记：树图DP | 拓扑排序 | SCC 缩点