Kosaraju 算法求强连通分量

原理

遍历两次 DFS，第一次遍历的时候按后序存储到数组里面，做记录。
第二次，从后往前按之前记录的数组，遍历所有这次没有被访问的点。

证明

云剪贴板 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

这个算法求出的东西是强连通分量

在第二次遍历中，我们按照了==从后往前==的顺序来进行遍历，这样做的意义，是保证在发现反向图中的一条边（y -> x）的时候（也就是原图中 x -> y），我们可以保证 y 是在 x 的后面的。因为后序遍历是按照：左儿子 -> 右儿子 -> 父亲 的顺序输出的，所以 y 在 x 的后面只有两种情况：

1. x 在搜索树中是 y 的儿子，也就是有一条边 y -> x，那么 x 和 y 就是连通块。
2. x 和 y 在搜索树中分别是左右儿子，但是这种情况就不可能有一条边 x -> y 了。

而且，连通块是可以==传导==的，如果 x 和 y 是强连通的，而且 y 和 z 是强连通的，那么 x 和 z 就是强连通的。

P2656 采蘑菇

思路

首先注意到由于每次都是向下取整，而且恢复系数都小于等于 $0.8$，那么我们可以得出每一条边在走若干次后一定等于 $0$，而且这个次数不会很多。

于是我们可以先求出强连通分量，我们发现在每个强连通块中都可以随便走，运用上面得出的东西我们可以发现一个强连通块中走若干次后一定可以把所有边都走到 $0$，那么我们可以把这个强连通块缩成一个有点权的点。

最后直接 BFS / SPFA 最长路就可以。

代码

#include <bits/stdc++.h>

using namespace std;
/*
*/
#define int long long
int n, m, s, cntSCC, vis[1000005], vis2[1000005], color[1000005], val[1000005];
struct Edge {
    int s, t, v, x;

};
vector <Edge> e[100005], e2[100005], e3[100005], v3[100005], scce[100005];
vector <int> path, SCCs[100005];
void dfs1(int nw) {
    vis[nw] = 1;
    for (auto to : e[nw]) {
        if (!vis[to.t]) dfs1(to.t);
    }
    path.push_back(nw);
}
void dfs2(int nw) {
    SCCs[cntSCC].push_back(nw);
    color[nw] = cntSCC;
    vis2[nw] = 1;
    for (auto to : e2[nw]) {
        if (!vis2[to.t]) dfs2(to.t), scce[cntSCC].push_back(to);
    }
}
void getSCC() {
    for (int i = 1; i <= n; i ++) {
        if (!vis[i]) dfs1(i);
    }
    // for (auto x : path) cout << x << "\n";
    for (int i = n; i >= 1; i --) {
        if (!vis2[path[i - 1]]) {
            cntSCC ++;
            // SCCs[cntSCC].push_back(i);
            dfs2(path[i - 1]);
        }
    }
}
int dis[1000005];
void spfa() {
    queue <int> q;
    memset(vis, 0, sizeof(vis));
    memset(dis, -1, sizeof(dis));
    s = color[s];
    q.push(s);
    dis[s] = val[s];
    vis[s] = 1;
    while (q.size()) {
        int nw = q.front();
        q.pop();
        vis[nw] = 0;
        for (auto to : e3[nw]) {
            if (dis[to.t] < dis[nw] + to.v) {
                dis[to.t] = dis[nw] + to.v;
                if (vis[to.t] == 0) {
                    vis[to.t] = 1;
                    q.push(to.t);
                }
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) {
        int x, y, z; double w;
        cin >> x >> y >> z >> w;
        e[x].push_back((Edge){x, y, z, w * 10});
        e2[y].push_back((Edge){y, x, z, w * 10});
        // oiwiki::g[x].push_back(y);
        // oiwiki::g2[y].push_back(x);
    }
    cin >> s;
    getSCC();
    // oiwiki::kosaraju();
    // cout << oiwiki::sccCnt << "\n";
    // cout << cntSCC << "\n";
    for (int i = 1; i <= n; i ++) {
        for (auto j : e[i]) {
            if (color[i] != color[j.t]) e3[color[i]].push_back((Edge){color[i], color[j.t], j.v + val[color[j.t]], j.x});
            else {
                int x = j.v, sum = 0;
                while (x) {
                    sum += x;
                    x = x * j.x / 10;
                } 
                val[color[i]] += sum;
            }
        }
    }
    // for (int i = 1; i <= cntSCC; i ++) {
    //     for (auto j : e3[i]) {
    //         cout << i << " " << j.t << "\n";
    //     }
    // }
    // newGraph();
    spfa();
    int ans = -1e9;
    sort(val + 1, val + cntSCC + 1);
    for (int i = 1; i <= cntSCC; i ++) {
        ans = max(ans, dis[i]);
        // cout << val[i] << "\n";
    }
    cout << ans << "\n";
    return 0;
}

扩展

可以思考一下如果题目还问：在现在的条件上最少走多少步，咋做。