$\operatorname{项链}$

题目链接：https://ac.nowcoder.com/acm/problem/213158

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109393205

题目

某天坐在电脑前打比赛的你被 Monster 抓到了一颗星球，并被强迫给它打工。
这颗星球上一共有 $n$ 个城市（编号 $1-n$ ），通过 $m$ 条单向道路连接（可能存在重边,但保证不存在环），在每个城市都有一颗宝石，第 $i$ 个城市宝石的价值为 $w_i$ 。一条项链的价值定义为某条路径上所有的宝石价值和，也即如果存在一条路径 $u \to v$ ，你可以利打造一条价值为 $\sum_u^v w_i$ 的项链。项链的价值可以为负，你也可以打造不含宝石的项链（价值为 $0$ ）。
你可以选择从任意一个城市开始，并沿着道路走下去直到尽头（没有边为止），每到一个城市你都会获得一颗宝石（包括初始位置，相同城市无法重复获得）。
最终你可能会有很多条项链，但你只需要交给 Monster 价值最高的那条，且 Monster 要求该项链的价值在所有可能得到的项链中价值最大。
作为报酬，Monster 允许你在剩余的项链中最多选择一条作为回报，你想要知道你和 Monster 的项链价值各是多少。

输入

共 $m+2$ 行：第一行两个整数 $n,m$ ，表示有 $n$ 个城市， $m$ 条道路。
第二行有 $n$ 个整数，第 $i$ 个整数数 $w_i$ 表示第 $i$ 个路口中宝石的价值。
接下来 $m$ 行每行两个整数 $u,v$ ，表示有一条 $u$ 到 $v$ 的单向路。

输出

共一行：两个整数 $ans1$ ， $ans2$ ，分别表示 Monster 和你项链的价值（中间用空格隔开）。

样例输入1

样例输出1

7 1

样例解释1

第一组样例，最优路径为 $1 \to 2 \to 3 \to 4$ ，你交出由 $1$ ， $2$ 号点宝石组成的项链（价值 $7$ ），得到 $4$ 号点宝石组成的项链。

样例输入2

6 8
-1 2 3 4 -5 6
1 4
4 5
4 6
5 6
5 2
2 3
5 3
3 6

样例输出2

11 4

样例解释2

第二组样例，最优路径为 $4 \to 5 \to 2 \to 3 \to 6$ ，交出项链 $2,3,6$ （价值 $11$ ）。收获 $4$ 。

数据范围

对于 $10\%$ 的数据， $n=10^5$ ，图呈现链状。
对于另外 $20\%$ 的数据， $n,m\leq 200$ ；
对于 $100\%$ 的数据， $1\leq n ,m\leq10^5,|w_i| \leq 10^9$ 。

思路

这道题是一道拓扑序上 dp 加 dfs。

我们先来看给 Monster 的怎么求。

那我们其实可以用一个拓扑序上的 dp： $sum[i]$ 表示从起点到这个点的前缀和。 $minn[i]$ 表示从起点到这个点中所有前缀和的最小值。
那我们可以看出，所有 $sum[i]-minn[i]$ 的最小值就是给 Monster 的答案。

接着看给自己的。

首先，众所周知，给自己的肯定是在给 Monster 所在的链的前面（就是走完给自己的再走给 Monster 的）或者后面（走完给 Monster 的再走给自己的），二者其中一个。
那我们又分开讨论：

在前面，那可以通过预处理求出来。
我们 dp 的时候设 $from[i]$ 为 $sum[i]-minn[i]$ 这一条链的起点的上面一个是哪个点。
那我们就可以得出这一条给 Monster 的链前面如果要给自己一条，是给 $maxn[from[i]]$ 。
（ $maxn[i]$ 就等于它与它的所有父亲的 $sum[i] - minn[i]$ 值的最大值，就是在上面的部分能组成的最长的链的长度）

接着我们看如何弄后面的部分。
其实可以直接 dfs，然后 dfs 里面直接用两个变量维护前面的 $sum$ 和 $minn$ 。
（不用弄数组，因为你是 dfs，可以回溯）
从你给 Monster 的链的结尾为开始 dfs 即可。

但是其实会有一个问题，就是可能会有不止一个链的值是你给 Monster 的链的值。
（就是可能会有很多种链都是最大值）
那我们就在一开始求给 Monster 的链时把都有最大值的链的尾部记录下来记录下来，然后到时一个一个枚举这些尾部，然后 dfs，找这些 dfs 里面值最大的一个和前面预处理求出来最大的取一个最大值，就是给自己的了。

比赛时

看到这道题，想了半天都不会，就打算打部分分（就是链的情况）：
就是直接扫过去求出值最大的区间，然后把区间中的值都赋成一个很小的负数，然后再扫一遍，两次分别扫出来的就是给 Monster 的和给自己的。
水了个 $10$ 分。

图片说明

代码

#include<queue>
#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

struct node {
    int to, nxt;
}e[100001];
int n, m, x, y, le[100001], KK, ru[100001], from[100001], now;
ll w[100001], ans1, ans2, sum[100001], minn[100001], re[100001], maxn[100001], rem[100001];
queue <int> q, ans;

void add(int x, int y) {
    e[++KK] = (node){y, le[x]}; le[x] = KK;
}

void dfs(int now, ll qjh, ll minsum) { 
    ans2 = max(ans2, qjh - minsum);

    if (rem[now] > qjh - minsum) return ;
    rem[now] = qjh - minsum;

    for (int i = le[now]; i; i = e[i].nxt)
        dfs(e[i].to, qjh + w[e[i].to], min(minsum, qjh + w[e[i].to]));
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%lld", &w[i]);
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        add(x, y);
        ru[y]++;
    }


    for (int i = 1; i <= n; i++) {
        sum[i] = re[i] = -1ll << 50;
        if (!ru[i]) {
            q.push(i);
            sum[i] = w[i];
            minn[i] = min(0ll, w[i]);
            re[i] = max(0ll, w[i]);
            ans1 = max(re[i], ans1);
            if (w[i] <= 0) from[i] = i;
                else from[i] = 0;
        }
    }

    while (!q.empty()) {
        now = q.front();
        q.pop();

        for (int i = le[now]; i; i = e[i].nxt) {
            if (re[e[i].to] <= sum[now] - minn[now] + w[e[i].to]) {
                re[e[i].to] = sum[now] - minn[now] + w[e[i].to];
                sum[e[i].to] = sum[now] + w[e[i].to];
                if (sum[e[i].to] > minn[now]) from[e[i].to] = from[now];
                    else from[e[i].to] = e[i].to;
                minn[e[i].to] = min(minn[now], sum[e[i].to]);
                maxn[e[i].to] = max(maxn[now], sum[e[i].to] - minn[e[i].to]);

                if (re[e[i].to] > ans1) {//找到有更优给 Monster 的
                    ans1 = re[e[i].to];
                    ans2 = maxn[from[e[i].to]];
                    //注意：这个不能是原来的 ans1，因为自己拿的和给 Monster 的要在同一条链上
                    while (ans.size()) ans.pop();
                    ans.push(e[i].to);//记录尾部
                }
                else if (re[e[i].to] == ans1) {//找到一样长的（可以给自己）
                    ans2 = max(ans2, maxn[from[e[i].to]]);//跟上面的一样要在同一条链上
                    ans.push(e[i].to);//记录所有最长的链的尾部
                }
            }

            ru[e[i].to]--;
            if (!ru[e[i].to]) q.push(e[i].to);
        }
    }

    while (!ans.empty()) {
        now = ans.front();
        ans.pop();

        for (int i = le[now]; i; i = e[i].nxt)
            dfs(e[i].to, 0, 0);//在后面里看有没有更优的给自己的链
    }

    printf("%lld %lld", ans1, ans2);

    return 0;
}