洛谷题单指南-树与图上的动态规划-P2656 采蘑菇

原题链接：https://www.luogu.com.cn/problem/P2656

题意解读：有向图中，有边权，重复走获得边权值乘上系数，系数只有一位小数，问从起点能走过的路径的最大边权和。

解题思路：

既然可以重复走，可以先求强联通分量，对强联通分量进行缩点，并计算缩点内所有路径反复走能得到的最大边权和。

由于缩点之后，就具备了拓扑序，直接通过拓扑序进行DP，即可求得从起点到每个点的最长路径。

最后更新答案即可。

要点：

1、提前将一条边反复走得到的权值和预处理出来，由于系数只有一位小数，可以乘10，再除10，即可取整

2、缩点的时候，如果两个点在同一个scc则更新缩点里的边权和，如果不在同一个scc则连边

3、可以对缩点图进行拓扑排序求最长路，直接基于缩点图编号是拓扑序逆序的性质进行DP更简单

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 80005, M = 400005;

int head1[N], head2[N], w[M], maxw[M], to[M], nxt[M], idx;
int dfn[N], low[N], timestamp;
stack<int> stk;
bool vis[N];
int scc[N], sz[N], cnt; //sz[i]表示i所在scc内的最大边权和，考虑反复走
int f[N];
int n, m, s, ans;

void add1(int a, int b, int c, int d)
{
    to[++idx] = b;
    w[idx] = c;
    while(c) maxw[idx] += c, c = c * d / 10; //计算一条边反复使用后的最大边权
    nxt[idx] = head1[a];
    head1[a] = idx;
}

void add2(int a, int b, int c)
{
    to[++idx] = b;
    w[idx] = c;
    nxt[idx] = head2[a];
    head2[a] = idx;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp;
    stk.push(u);
    vis[u] = true;
    for(int i = head1[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if(low[u] == dfn[u])
    {
        cnt++;
        while(true)
        {
            int t = stk.top(); stk.pop();
            vis[t] = false;
            scc[t] = cnt;
            if(t == u) break;
        }
    }
}

int main()
{
    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        double d;
        cin >> a >> b >> c >> d;
        add1(a, b, c, d * 10);
    }
    cin >> s;
    tarjan(s);

    for(int u = 1; u <= n; u++)
    {
        for(int i = head1[u]; i; i = nxt[i])
        {
            int v = to[i];
            int a = scc[u], b = scc[v];
            if(a && b && a != b)
            {
                add2(a, b, w[i]);
            }
            if(a && b && a == b) //边在同一个scc内，累加sz
            {
                sz[a] += maxw[i];
            }
        }
    }

    for(int u = cnt; u >= 1; u--)
    {
        if(!f[u]) f[u] = sz[u]; //如果没有被更新过，初始化为sz
        for(int i = head2[u]; i; i = nxt[i])
        {
            int v = to[i];
            if(f[u] + w[i] + sz[v] > f[v])
            {
                f[v] = f[u] + w[i] + sz[v];
            }
        }
    }

    for(int i = 1; i <= cnt; i++) ans = max(ans, f[i]);
    cout << ans;

    return 0;
}