Luogu P2656 采蘑菇 题解

(Updated: )
oi
, ,

Describe

题目链接

在一个 $N$ 个点， $M$ 条边的有向图中，每条路可以走无数次，边权为 $w_i$ ，边的恢复系数为 $p_i$ 第二次走时，边权变为 $w_i \times {p_i} $ ，第三次走时，边权变为 $w_i \times {p_i} ^ 2$…第 $k$ 次走时，边权变为 $w_i \times {p_i}^{k-1}$（全部向下取整，直到 $0$ 为止） 问，从 $S$ 出发，最大的路径经过的边权和为多少？(可以重复走) 对于所有数据，$N \leq 80,000 , M \leq 200,000 , 0.1\leq p_i \leq 0.8\text{且仅有一位小数},1\leq S \leq N$。

Solution

显然，只要我们找到一个环，那么我们就可以不停地走这个环，直到环内所有的边权为$0$，所以，只要找环，缩点再遍历一次就好了。

预处理

预处理出每条边的无限次走后的边权。

找环&缩点

看了下$Luogu$题解区内的都是$Tarjan$找环、缩点，那么对于我这种不会$Tarjan$的怎么办呢？当然是用$kosaraju$啦~ 什么是$kosaraju$？可以参考我的这篇博客(此文写的时间久远，写的不好勿喷)。

构图

找环&缩点后肯定是要重新构造一个有向无环图啦~ 那么怎么构图呢？ 直接暴力枚举每条边如果不是在同一个强连通分量，那么很遗憾这条边不能重复走很多次，那么就两个强连通分量间连接一条$w_i$的边即可。如果在同一个强连通分量，那么把所有在这个强连通分量中的所有边的无限次走后的边权的和存成点权。

遍历

最后从$S$出发跑个$dfs$就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#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]]);
}