Luogu1073 [NOIP2009]最优贸易

题目蓝链

Solution

因为可以随便走，所以显然就是一个缩点+DP，只需要记录每一个强联通分量的最大和最小价格就可以了

Code

#include <bits/stdc++.h>

using namespace std;

#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long LL;
typedef pair<int, int> pii;

inline int read() {
    int sum = 0, fg = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == ‘-‘) fg = -1;
    for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
    return fg * sum;
}

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;

vector<int> g[maxn], gg[maxn];

int n, m;
int Min[maxn], Max[maxn], a[maxn], f[maxn];
int d[maxn], low[maxn], dfn, S[maxn], top, pre[maxn], cnt, r[maxn], ans[maxn];
bool v[maxn];

void tarjan(int now) {
    d[now] = low[now] = ++dfn;
    S[++top] = now; v[now] = 1;
    for (int son : g[now]) {
        if (!d[son]) {
            tarjan(son);
            low[now] = min(low[now], low[son]);
        }else if (v[son]) low[now] = min(low[now], d[son]);
    }
    if (d[now] == low[now]) {
        cnt++;
        Max[cnt] = 0, Min[cnt] = inf;
        while (top) {
            int x = S[top--];
            pre[x] = cnt; v[x] = 0;
            Min[cnt] = min(Min[cnt], a[x]);
            Max[cnt] = max(Max[cnt], a[x]);
            if (x == now) break;
        }
    }
}

int main() {
#ifdef xunzhen
    freopen("trade.in", "r", stdin);
    freopen("trade.out", "w", stdout);
#endif

    n = read(), m = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= m; i++) {
        int x = read(), y = read(), z = read();
        g[x].push_back(y);
        if (z == 2) g[y].push_back(x);
    }

    for (int i = 1; i <= n; i++) if (!d[i]) tarjan(i);

    for (int i = 1; i <= n; i++)
        for (int j : g[i])
            if (pre[i] != pre[j]) gg[pre[i]].push_back(pre[j]), r[pre[j]]++;

    memset(f, 0x3f, sizeof f);
    queue<int> q;
    for (int i = 1; i <= cnt; i++)
        if (!r[i]) q.push(i);
    f[pre[1]] = Min[pre[1]];

    ans[pre[1]] = Max[pre[1]] - Min[pre[1]];
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int son : gg[now]) {
            if (f[now] < inf) {
                f[son] = min(min(f[son], f[now]), Min[son]);
                ans[son] = max(max(ans[son], ans[now]), Max[son] - f[son]);
            }
            r[son]--; if (!r[son]) q.push(son);
        }
    }

    printf("%d\n", ans[pre[n]]);

    return 0;
}

Summary

这道题网上有很多错误的题解，什么\(dijkstra\)还有\(spfa\)都是错的

除了洛谷有一个神奇的奇短无比的dfs好像是对的

Luogu1073 [NOIP2009]最优贸易

原文：https://www.cnblogs.com/xunzhen/p/9788257.html