Codeforces

Luogu

分析

显然一个强连通分量内的所有边都可以无限走，因此可以考虑缩点。

缩点后，每个强连通分量的权值设为内部所有边能得到的蘑菇个数之和，连接强连通分量的边的权值设为边上的蘑菇数，然后 DP 求最长路即可。

考虑怎么求边权为 $w$ 的边无限走能得到的蘑菇数。设这条边走了 $t$ 次后蘑菇变为 $0$，那么
$$
\frac{t(t+1)}{2}<w
$$
解得
$$
t=\left\lfloor\sqrt{2x+\frac{1}{4}}-\frac{1}{2}\right\rfloor
$$
那么能得到的蘑菇数是
$$
\begin{aligned}
&\sum_{i=0}^t\left(w-\sum_{j=0}^ij\right)\\
=&(t+1)w-\sum_{i=0}^t\frac{i(i+1)}{2}\\
=&(t+1)w-\left(\frac{t(t+1)(2t+1)}{12}+\frac{t(t+1)}{4}\right)\\
=&(t+1)w-\frac{t(t+1)(t+2)}{6}
\end{aligned}
$$

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,m;

struct sedge { int u,v,w; } se[N];

struct edge { int v,w,nxt; } e[N];
int head[N],ecnt=0;
inline void addEdge(int u,int v,int w) {
    e[++ecnt]=(edge){v,w,head[u]},head[u]=ecnt;
}

int dfn[N],low[N],tim=0,sta[N],in[N],top=0,bl[N],tot=0;
inline void tarjan(int u) {
    dfn[u]=low[u]=++tim,sta[++top]=u,in[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]) { ++tot;
        while (233) {
            int t=sta[top--]; in[t]=0,bl[t]=tot;
            if (u==t) break;
        }
    }
}

int w[N],dp[N];
inline int dfs(int u) {
    if (dp[u]) return dp[u];
    for (re int i=head[u];i;i=e[i].nxt)
        dp[u]=max(dp[u],e[i].w+dfs(e[i].v));
    return dp[u]+=w[u];
}

inline int calc(int w) {
    int t=sqrt(2*w+0.25)-0.5;
    return w*(t+1)-(t+1)*(t+2)*t/6;
}

signed main() {
    n=read(),m=read();
    for (re int i=1;i<=m;++i) {
        se[i]=(sedge){read(),read(),read()};
        addEdge(se[i].u,se[i].v,se[i].w);
    }
    for (re int i=1;i<=n;++i) if (!dfn[i]) tarjan(i);
    memset(head,0,sizeof(head)),ecnt=0;
    for (re int i=1;i<=m;++i) {
        int u=se[i].u,v=se[i].v;
        if (bl[u]==bl[v]) w[bl[u]]+=calc(e[i].w);
        else addEdge(bl[u],bl[v],e[i].w);
    }
    printf("%lld\n",dfs(bl[read()]));
    return 0;
}