P2656 题解

· · 题解

看到讨论区里说 dijkstra 不能求最长路，其实是可以求的，正好题解里没有一篇用 dijkstra 的，那我就来水发一篇吧

Description

给定一个 n 个点 m 条边的有向图，每条边有一个边权与一个“恢复系数”，当重复经过一条边时这条边的边权计算为上次经过这条边时的边权乘上这个“恢复系数”再向下取整，求从某个给定的 s 点出发，经过的边权之和最大值。

Solution

Tarjan 缩点不用说，在一个强连通分量里我们可以把每条边的边权“榨干”，也就是重复走直到这个强连通分量里的每一条边对答案不再有贡献为止。

而众所周知，dij 在求最长路时是不能有正环的，否则会陷在正环中无限循环。而 Tarjan 缩点之后就很好地避免了这个问题，因为一个正环一定在一个强连通分量中，在缩点之后就被缩成了一个点。至于具体实现，只需将原来求最短路中的松弛条件 dis[y] > dis[x] + e[i].w 改为 dis[y] < dis[x] + en[i].w + val[y] 就可以了，其中 val[y] 表示编号为 y 的强连通分量中所有边权对答案可以做出的最大贡献之和（也就是将这里面的每一条边“榨干”之后的贡献之和）。

Code

完整版高清有注释代码：

#include<iostream>
#include<queue>
#include<stack>
#define maxn 80004
#define maxm 200005
#define inf 0x7fffffff
using namespace std;
int n, m, s;
double re[maxm];
int head[maxn], cnt, headn[maxn], cntn;
struct edge {
    int to, next, w, maxx;
    double r;
}e[maxm], en[maxm];
inline void add(int u, int v, int w, double r, int maxx) {
    e[++ cnt] = (edge){v, head[u], w, maxx, r};
    head[u] = cnt;
}//其实那个 r 没有什么用，但我懒得改了
inline void addn(int u, int v, int w, double r, int maxx) {
    en[++ cntn] = (edge){v, headn[u], w, maxx, r};
    headn[u] = cntn;
}
inline int maxx(int w, int r) {
    int now = (r * w) / 10; int ans = w;
    while(now) {
        ans += (int)now;
        now = (r * now) / 10;//避免精度问题
    }
    return ans;
}//求这条边所能贡献的最大边权和
stack<int> st;
int dfn[maxn], low[maxn], ind, belong[maxn], col, val[maxn];
bool vis[maxn];
void tar(int u) {
    dfn[u] = low[u] = ++ ind;
    st.push(u); vis[u] = 1;
    for(int i = head[u], v; i; i = e[i].next) {
        v = e[i].to;
        if(dfn[v] == 0) {
            tar(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v]) low[u] = min(low[u], low[v]);
    }
    if(low[u] == dfn[u]) {
        ++ col; int t = -1;
        while(t != u) {
            t = st.top(); st.pop();
            belong[t] = col; vis[t] = 0;
        }
    }
}
struct node {
    int pos, dis;
    bool friend operator < (node a, node b) {return a.dis > b.dis;}
    //注意求最长路时重定义运算符是是大于号
};
priority_queue<node> q;
bool viss[maxn];
int dis[maxn];
void dij() {
    for(int i = 1; i <= col; ++ i) dis[i] = 0;
    s = belong[s]; dis[s] = val[s];//走到起点时最大答案就是这个强连通分量的最大边权之和
    q.push((node){s, dis[s]});
    while(!q.empty()) {
        node tmp = q.top(); q.pop();
        int x = tmp.pos;
        if(vis[x]) continue;
        for(int i = headn[x]; i; i = en[i].next) {
            int y = en[i].to;
            if(dis[y] < dis[x] + en[i].w + val[y]) {//dijkstra魔改的地方
                dis[y] = dis[x] + en[i].w + val[y];
                if(!vis[y]) {
                    q.push((node){y, dis[y]});
                }
            }
        }
    }
}
int main() {
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);//读入优化
    cin >> n >> m; double r;
    for(int i = 1, u, v, w; i <= m; ++ i) {
        cin >> u >> v >> w >> r;
        add(u, v, w, r, maxx(w, r * 10));
    }
    cin >> s;
    for(int i = 1; i <= n; ++ i) {
        if(dfn[i] == 0) tar(i);
    }
    for(int j = 1; j <= n; ++ j) {
        for(int i = head[j], v; i; i = e[i].next) {
            v = e[i].to;
            if(belong[j] == belong[v]) {
                val[belong[j]] += e[i].maxx;
                continue;
            }
            addn(belong[j], belong[v], e[i].w, e[i].r, e[i].maxx);
        }
    }
    dij(); 
    int ans = -inf;
    for(int i = 1; i <= col; ++ i) ans = max(ans, dis[i]);
    cout << ans;
    return 0;
}