洛谷P4742 [Wind Festival]Running In The Sky 题解

题目链接：P4742 [Wind Festival]Running In The Sky

题意：

一天的活动过后，所有学生都停下来欣赏夜空下点亮的风筝。cxy 想要以更近的视角感受一下，所以她跑到空中的风筝上去了（这对于一个妹子来说有点匪夷所思）！每只风筝上的灯光都有一个亮度 \(k_i\) 。由于风的作用，一些风筝缠在了一起。但是这并不会破坏美妙的气氛，缠在一起的风筝会将灯光汇聚起来，形成更亮的光源！

cxy 已经知道了一些风筝间的关系，比如给出一对风筝 \((a,b)\) ，这意味着她可以从 \(a\) 跑到 \(b\) 上去，但是不能返回。

现在，请帮她找到一条路径（她可以到达一只风筝多次，但只在第一次到达时她会去感受上面的灯光），使得她可以感受到最多的光亮。同时请告诉她这条路径上单只风筝的最大亮度，如果有多条符合条件的路径，输出能产生最大单只风筝亮度的答案。

输入格式：

第一行两个整数 \(n\) 和 \(m\) 。\(n\) 是风筝的数量，\(m\) 是风筝间关系对的数量。

接下来一行 \(n\) 个整数 \(k_i\) 。

接下来 \(m\) 行，每行两个整数 \(a\) 和 \(b\) ，即 cxy 可以从 \(a\) 跑到 \(b\) 。

输出格式：

一行两个整数。cxy 在计算出的路径上感受到的亮度和，这条路径上的单只风筝最大亮度。

数据范围：

\(0<n\le2\times10^5,\ 0<m\le5\times10^5,\ 0<k\le200\) 。

因为一个点可以多次走，所以在同一个强连通分量内的所有点都能走到，并从任意一个点出来。

考虑缩点后dp。设 \(f_i,g_i\) 分别表示（缩点后的）点 \(i\) 的最大总和和取到最大总和时的路径上节点的最大值。

初值 \(f_i = \sum \mathtt{val}_i, g_i = \max \mathtt{val}_i\) 。转移代码如下：

if(f[u] + sum[v] > f[v])
{
    f[v] = f[u] + sum[v]; up(g[v] = mx[v], g[u]);
}else if(f[u] + sum[v] == f[v]) up(g[v], g[u]);

注意如果 \(f_v\) 被更新了，\(g_v\) 就不能使用当前的值，也就是 \(g_v \gets (\mathtt{mx}_v\uparrow g_u)\)

提示：

\(\mathtt{Tarjan}\) 缩点后的点以逆拓扑序编号。
养成好习惯，判重边（要边权的除外）。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))
#define M ((int)(5e5 + 15))

bitset<N> ins;
int n,m,pos=1,val[N],used[N],head[N],f[N],g[N],sum[N],mx[N];
int scnt,stktop,dfn[N],scc[N],low[N],stk[N],top[N];
struct Edge { int u,v,next; } e[M];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void Tarjan(int u)
{
    static int tim = 0;
    dfn[u] = low[u] = ++tim; ins[u] = 1; stk[++stktop] = u;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v;
        if(!dfn[v])
        {
            Tarjan(v); down(low[u], low[v]);
        }else if(ins[v]) down(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        top[++scnt] = u;
        for(int p = 0; p != u; )
        {
            p = stk[stktop--]; sum[scnt] += val[p];
            up(mx[scnt], val[p]); ins[p] = 0; scc[p] = scnt;
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> val[i];
    for(int i=1,u,v; i<=m; i++) { cin >> u >> v; addEdge(u,v); }
    for(int i=1; i<=n; i++) if(!dfn[i]) Tarjan(i);
    for(int i=1; i<=n; i++) head[i] = 0; pos = 1;
    for(int i=1; i<=scnt; i++){ f[i] = sum[i]; g[i] = mx[i]; }
    for(int i=2,u,v; i <= m + 1; i++)
    {
        u = scc[e[i].u], v = scc[e[i].v];
        if(u != v) addEdge(u,v);
    }
    for(int u = scnt; u; u--)
    {
        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if(used[v] == u) continue; used[v] = u;
            if(f[u] + sum[v] > f[v])
            {
                f[v] = f[u] + sum[v]; up(g[v] = mx[v], g[u]);
            }else if(f[u] + sum[v] == f[v]) up(g[v], g[u]);
        }
    }
    int p = max_element(f + 1, f + 1 + n) - f;
    cout << f[p] << ' ' << g[p] << '\n';
    return 0;
}