[Luogu P2656 采蘑菇] Solution

Problem Link: P2656 采蘑菇

Problem Statement:

q779 and cxy are going to a forest to pick mushrooms.

There are $N$ bushes in the forest and $M$ trails, each of which is a one-way path connecting two bushes with a certain number of mushrooms. q779 and cxy can pick all the mushrooms on a path by passing it once. Since the forest is a magically fertile land, after the mushrooms on a path are picked, new mushrooms will grow, multiplying the number of mushrooms by the “recovery factor” of the path $c$ and rounding down.

For example, if there are $4$ mushrooms on a path and the “recovery factor” of the path is $c = 0.7$, then the number of mushrooms that can be picked from the first to the fourth time through the path is $4,2,1,0$ respectively.

Now, q779 and cxy start from bush $S$ and find the maximum number of mushrooms they can pick.

Input:

Two integers, $N$ and $M$, in the first row.

The second to $M+1$ rows, four numbers per row, denote the starting point, the ending point, the initial number of mushrooms and the recovery factor of a trail, respectively.

In the $M+2$ th row, an integer $S$.

Output:

One integer in a row indicates the maximum number of mushrooms that can be picked, ensuring that the answer does not exceed $2^{31}-1$.

Data range:

$1 \le N\le 8\times 10^4,~1\le M\le 2\times 10^5,~0\le c\le 0.8$ and up to one decimal, $1\le S\le N$.

The first problem solution after the resurrection, also a warm-up question.

Anyway, may my dream come true in NOIP.

Notice that an edge can be walked an infinite number of times,

then any strongly connected component can be walked until it does not grow mushrooms.

Consider shrinking points and preprocessing the answer for each strongly connected component

Then it becomes simple “do topo+dp on DAG”

The time complexity is $\mathcal{O}(m \log_{\frac{4}{5}} M)$, in short, can be passed.

code:

#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;
}

It is a bit difficult to translate the solution into English, but I will try.

There was a phrase here in the Chinese solution, but I’m not going to translate it.