Luogu P2656 采蘑菇 题解

#include<bits/stdc++.h>
#define LD double
using namespace std;
inline int read(){
    int res=0,f=1;char ch=getchar();
    while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') res=res*10+ch-'0',ch=getchar();
    return res*f;
}
struct edge{int u,v,w;}e[200010];
int n,m,fir[80010],nxt[200010],son[200010],w[200010],tot,sum[200010],val[200010],S,dis[80010],vis[80010],d[80010],t;
vector<int> G[80010],P[80010];
inline void add(int x,int y,int z){++tot;nxt[tot]=fir[x];fir[x]=tot;son[tot]=y;w[tot]=z;}
inline void dfs1(int x){
    vis[x]=1;
    for(auto i:G[x])//C++11简易写法
        if(!vis[i]) dfs1(i);
    d[++t]=x;
}
inline void dfs2(int x){
    vis[x]=t;
    for(auto i:P[x])
        if(!vis[i]) dfs2(i);
}
inline void kosaraju(){//缩点
    memset(vis,0,sizeof(vis));t=0;
    for(int i=1;i<=n;i++)
        if(!vis[i]) dfs1(i);
    memset(vis,0,sizeof(vis));t=0;
    for(int i=n;i>=1;i--)
        if(!vis[d[i]]) ++t,dfs2(d[i]);
}
inline void dfs(int x){
    if(dis[x]) return ;
    dis[x]=val[x];//别忘记加上点权
    int Max=0;
    for(int to,i=fir[x];i;i=nxt[i]){
        to=son[i];
        dfs(to);
        Max=max(Max,dis[to]+w[i]);
    }
    dis[x]+=Max;
}
int main(){
    n=read();m=read();
    for(int x,y,w,i=1;i<=m;i++){
        x=read();y=read();w=read();
        e[i]=(edge){x,y,w};
        G[x].push_back(y);
        P[y].push_back(x);//缩点需要建反边
        LD s;scanf("%lf",&s);
        while(w){//预处理出无限次走的边权
            sum[i]+=w;
            w=(LD)w*s;
        }
    }
    kosaraju();
    for(int i=1;i<=m;i++)
        if(vis[e[i].u]!=vis[e[i].v]) add(vis[e[i].u],vis[e[i].v],e[i].w);//不在同一个强连通分量，构图
        else val[vis[e[i].u]]+=sum[i];//在同一个强连通分量，累计点权
    S=read();
    dfs(vis[S]);//最后跑一次dfs求最大值
    printf("%d\n",dis[vis[S]]);
}