洛谷P2656 采蘑菇题解

题意：

q779 和 cxy 要去森林采蘑菇。

森林间有 \(N\) 个小树丛，\(M\) 条小径，每条小径都是单向的，连接两个小树丛，上面都有一定数量的蘑菇。q779 和 cxy 经过某条小径一次，可以采走这条路上所有的蘑菇。由于森林是一片神奇的沃土，所以一条路上的蘑菇被采过后，又会长出一些新的蘑菇，数量为原来蘑菇的数量乘上这条路的“恢复系数” \(c\) ，再下取整。

比如，一条路上有 \(4\) 个蘑菇，这条路的“恢复系数”为 \(c = 0.7\)，则第一~四次经过这条路径所能采到的蘑菇数量分别为 \(4,2,1,0\) 。

现在，q779 和 cxy 从 \(S\) 号小树丛出发，求他们最多能采到多少蘑菇。

输入格式：

第一行两个整数，\(N\) 和 \(M\)。

第二行到第 \(M+1\) 行，每行四个数，分别表示一条小路的起点、终点、初始蘑菇数和恢复系数。

第 \(M+2\) 行，一个整数 \(S\)。

输出格式：

一行一个整数，表示最多能采到多少蘑菇，保证答案不超过 \(2^{31}-1\)。

数据范围：

\(1 \le N\le 8\times 10^4,~1\le M\le 2\times 10^5,~0\le c\le 0.8\) 且最多有一位小数， \(1\le S\le N\)。

复活后的第一篇题解，~~也是一道热身题~~。无论如何，愿我圆梦NOIP。

注意到一条边可以走无数遍，那么任何强连通分量都可以走到不长蘑菇为止。

考虑缩点并预处理每个强连通分量的答案，然后就变成简单的 DAG 上跑 topo+dp 了

时间复杂度 \(\mathcal{O}(m \log_{\frac{4}{5}} M)\) ，总之能过

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(8e4 + 15))
#define M ((int)(2e5 + 15))

int n,m,s,pos=1,scnt,stktop,head[N],f[N],g[N];
int dfn[N],low[N],stk[N],scc[N],val[N]; bitset<N> ins;
struct Edge { int u,v,w,c,next; } e[M];
void addEdge(int u,int v,int w,double c)
{ e[++pos] = {u,v,w,(int)(c * 10),head[u]}; head[u] = pos; }
void Tarjan(int u)
{
    static int tim = 0;
    dfn[u] = low[u] = ++tim; ins[u] = 1; stk[++stktop] = u;
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; if(!dfn[v])
        {
            Tarjan(v); down(low[u], low[v]);
        }else if(ins[v]) down(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        ++scnt;
        for(int p = 0; p != u; )
        { p = stk[stktop--]; ins[p] = 0; scc[p] = scnt; }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v,w; i<=m; i++)
    {
        static double c;
        cin >> u >> v >> w >> c; addEdge(u,v,w,c);
    }
    cin >> s; Tarjan(s);
    pos = 1; for(int i=1; i<=n; i++) head[i] = 0;
    for(int i=2; i <= m+1; i++)
    {
        int u = scc[e[i].u], v = scc[e[i].v];
        if(!(u && v)) continue;
        if(u != v) addEdge(u,v,e[i].w,-1);
        else while(e[i].w){ g[u] += e[i].w; e[i].w = e[i].w * e[i].c / 10; }  
    }
    // for(int i=1; i<=scnt; i++) cout << f[i] << " \n"[i==scnt];
    // for(int i=2; i<=pos; i++) cout << e[i].u << ' ' << e[i].v << ' ' << e[i].w << '\n';
    for(int u = scnt; u; u--)
    {
        if(!f[u]) f[u] = g[u];
        for(int i=head[u]; i; i=e[i].next)
        { int v = e[i].v; up(f[v], f[u] + e[i].w + g[v]); }
    }
    cout << *max_element(f + 1, f + 1 + scnt) << '\n';
    return 0;
}