Tarjan缩点+拆点+Spfa最长路

解题思路

  • 缩点。显然,进入一个强连通分量,可以把里面的边全部走满
  • 拆点,分为入点和出点
  • 建图

    • 对于不同强连通分量的边,正常建,边权为走一次的边权,注意是入点连出点
    • 对于相同强连通分量的边,把走满的边权加到连接这个点入点和出点的边权上
  • 从起点的入点Spfa最长路,就可以不用考虑点权了。然后在所有出点中找距离最长的。

代码

#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;

const int MAXN = 8e4 + 5;
const int MAXM = 2e5 + 5;

struct Edge{
    int to, val;
    Edge *nxt;

    Edge(int to, int val, Edge *nxt) : to(to), val(val), nxt(nxt) {}
};

Edge *hd1[MAXN], *hd2[MAXN];

void Add1(int u, int v, int w) {
    hd1[u] = new Edge(v, w, hd1[u]);
}

void Add2(int u, int v, int w) {
    hd2[u] = new Edge(v, w, hd2[u]);
}

int n, m;
int inx[MAXM], iny[MAXM], inz[MAXM];
double inr[MAXM];
int low[MAXN], col[MAXN], dfn[MAXN], tc, tot;
stack<int> stk;
int w[MAXN << 1], dis[MAXN << 1];
bool vis[MAXN << 1];

void Tarjan(int u) {
    stk.push(u); dfn[u] = low[u] = ++tc;
    for (Edge *e = hd1[u]; e; e = e->nxt) {
        int v = e->to;
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else {
            if (!col[v]) low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        col[u] = ++tot;
        while (!stk.empty()) {
            int v = stk.top(); stk.pop();
            col[v] = tot;
            if (v == u) break;
        }
    }
}

int GetTotal(int x, double y) {
    int ret = 0;
    while (x) {
        ret += x;
        x = (int)floor((double)x * y);
    }
    return ret;
}

int Id(int u, int typ) {
    if (typ == 0) return col[u];
    else return col[u] + tot;
}

void Rebuild() {
    for (int i = 1; i <= m; i++) {
        if (col[inx[i]] == col[iny[i]]) w[col[inx[i]]] += GetTotal(inz[i], inr[i]);
        else Add2(Id(inx[i], 1), Id(iny[i], 0), inz[i]);
    }
    for (int i = 1; i <= tot; i++) Add2(i, i + tot, w[i]);
}

void Spfa(int s) {
    memset(dis, 0x8f, sizeof(dis));
    queue<int> q; q.push(s); dis[s] = 0; vis[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = false;
        for (Edge *e = hd2[u]; e; e = e->nxt) {
            int v = e->to;
            if (dis[v] < dis[u] + e->val) {
                dis[v] = dis[u] + e->val;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> inx[i] >> iny[i] >> inz[i] >> inr[i];
        Add1(inx[i], iny[i], inz[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) Tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        cerr << col[i] << ' ';
    }
    cerr << endl;
    Rebuild();
    int s;
    cin >> s;
    Spfa(Id(s, 0));
    int ans = 0;
    for (int i = 1; i <= tot * 2; i++) ans = max(ans, dis[i]);
    cout << ans << endl;
    return 0;
}