题解：P1073

iamajcer · 2025-07-14 10:31:00 · 题解

思路

题解里都是跑分层图或者 tarjan 缩点后用贪心，需要跑两次图确定连通性。这里我提供一种不一样的 tarjan 思路。

先缩点，然后考虑拓扑后 DP。

先考虑缩点需要存什么信息，贪心的想，肯定存水晶球的最低价 mn_u 和最高价 mx_u，低买高卖嘛，所以其余的信息都无所谓了。

再考虑如何 DP。令 f_{u, 0/1/2} 表示遍历到 u 点，0，1，2 分别代表当前没有/持有/已经卖出并且保证不会再买入水晶球，所能赚的最大利润。

然后正常转移就好。转移方程是好推的，这里列出方便看。注意不要漏情况就好。

假如从 u 遍历到 v，那么有：

就做完了吗？并没有。拓扑排序如何进行？此题给定的起点与终点，而不是对于整张图的。

我们可以从起点开始 dfs，把无法到达的点删去，此时再对于整张图跑拓扑就好。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100005;

int n, m, u1, v1, op, val[N], dfn[N], low[N], tim=0;
int cnt=0, id[N], mn[N], mx[N], f[N][3], vis[N], d[N];
stack<int> stk;
queue<int> q;
vector<int> a[N], b[N], c[N];
void tarjan(int u)
{
    dfn[u]=low[u]=++tim, stk.push(u);
    for (int i=0; i<a[u].size(); i++)
    {
        int v=a[u][i];
        if (!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u], low[v]);
        }
        else if (!id[v]) low[u]=min(low[u], dfn[v]);
    }

    if (low[u]==dfn[u])
    {
        cnt++;
        while (stk.top()!=u) id[stk.top()]=cnt, mn[cnt]=min(mn[cnt], val[stk.top()]), mx[cnt]=max(mx[cnt], val[stk.top()]), stk.pop();
        id[stk.top()]=cnt, mn[cnt]=min(mn[cnt], val[stk.top()]), mx[cnt]=max(mx[cnt], val[stk.top()]), stk.pop();
    }
}
void dfs(int u)
{
    if (vis[u]) return ;
    vis[u]=1;

    for (int i=0; i<b[u].size(); i++) dfs(b[u][i]);
}
void top()
{
    for (int i=1; i<=cnt; i++) if (!d[i]) q.push(i);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();

        for (int i=0; i<c[u].size(); i++)
        {
            int v=c[u][i];
            f[v][0]=max(f[v][0], f[u][0]);
            f[v][1]=max({f[v][1], f[u][0]-mn[v], f[u][1]});
            f[v][2]=max({f[v][2], f[u][1]+mx[v], f[u][2], mx[v]-mn[v]});

            d[v]--;
            if (!d[v]) q.push(v);
        }
    }
}
int main()
{
//  freopen("P1073_16.in", "r", stdin);

    memset(mn, 63, sizeof mn);

    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++) scanf("%d", &val[i]);
    for (int i=1; i<=m; i++)
    {
        scanf("%d%d%d", &u1, &v1, &op);
        a[u1].push_back(v1);
        if (op==2) a[v1].push_back(u1);
    }
    for (int i=1; i<=n; i++) if (!dfn[i]) tarjan(i);
    for (int u=1; u<=n; u++)
        for (int j=0; j<a[u].size(); j++)
        {
            int v=a[u][j];
            if (id[u]!=id[v]) b[id[u]].push_back(id[v]);
        }

    dfs(id[1]);
    for (int u=1; u<=n; u++)
    {
        if (!vis[u]) continue;
        for (int j=0; j<b[u].size(); j++)
        {
            int v=b[u][j];
            if (u!=v) c[u].push_back(v), d[v]++;
        }
    }

    for (int i=1; i<=cnt; i++) f[i][0]=f[i][1]=-1000000000;
    f[id[1]][0]=0, f[id[1]][1]=-mn[id[1]], f[id[1]][2]=mx[id[1]]-mn[id[1]];
    top();

    printf("%d", max({f[id[n]][0], f[id[n]][1], f[id[n]][2], 0}));
    return 0;
}