「NOIP 2009」最优贸易

#图论 #最短路 #SPFA
Published on 2016-11-07

描述

给定一个 n(n≤105)n(n\le {10}^5) 个点，m(m≤106)m(m\le {10}^6) 条边的有向图，每个点有一个价格 pi(1≤vi≤100)p_i(1\le v_i\le 100)，求一条 11 到 nn 的路径 ，使得 vj−vi(1≤i≤j≤k)v_j - v_i(1\le i \le j\le k) 最大。请你输出这个最大值。

分析

对于每一个点 ii，求出 mni\mathrm{mn}_i 为从 11 出发到 ii，能经过的点的最低价格。mxi\mathrm{mx}_i 为从 ii 出发到 nn，能经过的点的最高价格。那么答案就是 ∑1≤i≤nmxi−mni\sum_{1\le i\le n}\mathrm{mx}_i - \mathrm{mn}_i。

考虑怎么计算 mni\mathrm{mn}_i（求 mxi\mathrm{mx}_i 只需要将边反向，从 nn 出发类似的求计算）。我们使用类 SPFA 算法：先将 d0d_0 设置为 p0p_0，其余均为 ∞\infty，然后将 00 入队。每次出队一个点 uu，遍历它能到的点 vv，如果 dv>dud_v > d_u，那么更新 dv=min(du,pv)d_v = \min(d_u, p_v)，如果 vv 不在队中，那么入队。
算法的正确性不难理解，这也算是 SPFA 算法的一个扩展，由于题目中的式子满足三角不等式，所以我们可以利用 SPFA 来迭代求解，详见：SPFA算法的优化及应用。

代码

//  Created by Sengxian on 2016/11/7.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  Vijos 1754 SPFA
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 100000 + 3, MAX_M = 500000 + 3, MAX_V = 100 + 3;

struct edge {
    edge *next;
    int to;
    edge(edge *next = NULL, int to = 0): next(next), to(to) {}
} pool[MAX_M * 4], *pit = pool, *first[MAX_N], *rFirst[MAX_N];

int n, m, price[MAX_N], mn[MAX_N], mx[MAX_N];

inline bool tension(int &a, const int &b) {
    return b < a ? a = b, true : false;
}

void SPFA(int s, int dis[], edge *first[], int sgn = 1) {
    static bool inq[MAX_N];
    static int q[MAX_N];
    memset(inq, 0, sizeof inq);
    memset(dis, 0x3f, sizeof (int) * n);
    int l = 0, r = 0;
    q[r++] = s;
    dis[s] = price[s] * sgn;
    while (r - l >= 1) {
        int u = q[(l++) % n];
        inq[u] = false;
        for (edge *e = first[u]; e; e = e->next) {
            if (tension(dis[e->to], dis[u]) && !inq[e->to]) {
                dis[e->to] = min(dis[e->to], price[e->to] * sgn);
                q[(r++) % n] = e->to, inq[e->to] = true;
            }
        }
    }
}

int main() {
    n = ReadInt(), m = ReadInt();
    for (int i = 0; i < n; ++i) price[i] = ReadInt();
    for (int i = 0, u, v, w; i < m; ++i) {
        u = ReadInt() - 1, v = ReadInt() - 1, w = ReadInt();
        first[u] = new (pit++) edge(first[u], v);
        rFirst[v] = new (pit++) edge(rFirst[v], u);
        if (w == 2) {
            first[v] = new (pit++) edge(first[v], u);
            rFirst[u] = new (pit++) edge(rFirst[u], v);    
        }
    }
    SPFA(0, mn, first, 1), SPFA(n - 1, mx, rFirst, -1);
    int ans = 0;
    for (int i = 0; i < n; ++i) ans = max(ans, -mx[i] - mn[i]);
    printf("%d\n", ans);
    return 0;
}
「NOIP 2010」引水入城