题解 P1073 【最优贸易】

· · 题解

首先看到这道题发现是有环而且是要求最大值的 想到tarjan + dp

先考虑DAG上的DP

转移方程式也就比较简单了 预处理出来$minn[v] = min (minn[u], a[u]) f[i] = max(f[i], a[i] - minn[i]);

能过 50%

然后开始想正解

先缩点 在DAG上dp

然后就是模板题了吧 比较的easy

缩点的时候记录一下每个环上的最小值 & 最大值

记为minn[i] maxx[i]

在tarjan缩点的时候只要加一步操作即可

   if (low[u] == dfn[u]) {
        scc_cnt ++ ;
        while (s[top + 1] != u) {
            scc_num[s[top]] = scc_cnt;
            minn[scc_cnt] = min(minn[scc_cnt], a[s[top]]);
            maxx[scc_cnt] = max(maxx[scc_cnt], a[s[top]]);
            vis[s[top -- ]] = 0;
        }
    }

然后这个dp状态转移方程式也需要变化一下

f[i] = max(f[i], max[scc_num[i]] - minn[i])

然后这个算法还可以常数优化一下 不知道算不算

f[i]$顺便记录下前缀最大值 那么答案就是$f[scc_num[i]]

实现起来完全就是tarjan模板题

code

//
//  P1073 最优贸易 trade.cpp
//  Tarjan
//
//  Created by Hock on 2019/10/2.
//  Copyright © 2019 Hock. All rights reserved.
//

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <cstring>

using namespace std;

typedef unsigned long long ll;

const int INF = 2139062143;

#define DEBUG(x) std::cerr << #x << ' = ' << x << std::endl

inline int read() {
    int f = 1, x = 0;char ch;
    do {ch = getchar();if (ch == '-')f = -1;} while (ch > '9' || ch < '0');
    do {x = x * 10 + ch - '0';ch = getchar();} while (ch >= '0' && ch <= '9');
    return f * x;
}

const int MAX_M = 500000 + 5;

struct EDGE {
    int to, next;
} edge[MAX_M];

int head[MAX_M], cnt;

void addedge (int u, int v) {
    edge[++cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt;
}

int dfn[MAX_M], low[MAX_M], vis[MAX_M], s[MAX_M], top, f[MAX_M];

int n, m, scc_num[MAX_M], in[MAX_M], out[MAX_M], scc_cnt;

int minn[MAX_M], maxx[MAX_M], a[MAX_M], x[MAX_M], y[MAX_M];

void tarjan (int u) {
    dfn[u] = low[u] = ++cnt;
    vis[u] = 1;
    s[++top] = u;
    for (int i = head[u]; i; i = edge[i].next) {
        int v = edge[i].to;
        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]) {
        scc_cnt ++ ;
        while (s[top + 1] != u) {
            scc_num[s[top]] = scc_cnt;
            minn[scc_cnt] = min(minn[scc_cnt], a[s[top]]);
            maxx[scc_cnt] = max(maxx[scc_cnt], a[s[top]]);
            vis[s[top -- ]] = 0;
        }
    }
}

void DP (int s) {
    queue < int > q;
    q.push(scc_num[s]);
    f[scc_num[s]] = max(f[scc_num[s]], maxx[scc_num[s]] - minn[scc_num[s]]);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].to;
            in[v] -- ;
            minn[v] = min(minn[v], minn[u]);//前缀最小值
            f[v] = max(max(f[u], maxx[v] - minn[v]), f[v]);
            if (!in[v])
                q.push(v);
        }
    }
}

int main () {
    n = read(); m = read();
    for (int i = 1; i <= n; i ++ ) a[i] = read();
    for (int i = 1; i <= m; i ++ ) {
        int u = read(), v = read(), opt = read();
        if (opt == 1) {
            addedge (u, v);
            x[cnt] = u;
            y[cnt] = v;
        }
        if (opt == 2) {
            addedge (u, v);
            addedge (v, u);
        }
    }
    m = cnt;
    memset (minn, 127, sizeof(minn));
    memset (maxx, -127, sizeof(maxx));
    cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (!dfn[i]) tarjan(i);
    cnt = 0;
//    puts("");
//    cout << "scc_cnt = " << scc_cnt << endl;
    memset (head, 0, sizeof(head));
    memset (edge, 0, sizeof(edge));
    for (int i = 1; i <= m; i ++ ) {
        if (scc_num[x[i]] != scc_num[y[i]]) {
            addedge (scc_num[x[i]], scc_num[y[i]]);
            in[scc_num[y[i]]] ++ ;
        }
    }
//    for (int i = 1; i <= n; i ++ ) {
//        cout << minn[scc_num[i]] << " " << maxx[scc_num[i]] << "\n";
//    }
    DP(1);
//    if (f[scc_num[n]] < 0) f[scc_num[n]] = 0;
    cout << f[scc_num[n]] << endl;
    return 0;
}