最优贸易

AcWing-341-最优贸易

分析

见《进阶指南》第357页。

实现

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 100010, M = 500010;
struct edge {
    int to, next;
};
edge e[2 * M];
int idx, head[N];
struct node {
    int u, v, k;
};
node rec[M];
int n, w[N], m;
int b[N], s[N];
bool mark[N];

void add_edge (int u, int v) {
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void spfa1 () {
    memset(mark, 0, sizeof(mark));
    memset(b, 0x3f, sizeof(b));
    b[1] = w[1];
    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        mark[cur] = false;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to;
            if (min(b[cur], w[to]) < b[to]) {
                b[to] = min(b[cur], w[to]);
                if (mark[to] == false) {
                    q.push(to);
                    mark[to] = true;
                }
            }
        }
    }
}
void spfa2() {
    memset(mark, 0, sizeof(mark));
    memset(s, -0x3f, sizeof(s));
    s[n] = w[n];
    queue<int> q;
    q.push(n);
    mark[n] = true;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        mark[cur] = false;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to;
            if (max(s[cur], w[to]) > s[to]) {
                s[to] = max(s[cur], w[to]);
                if (mark[to] == false) {
                    q.push(to);
                    mark[to] = true;
                }
            }
        }
    }
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", &w[i]);
    for (int i = 1; i <= m; ++ i) scanf("%d%d%d", &rec[i].u, &rec[i].v, &rec[i].k);

    idx = 0;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; ++ i) {
        add_edge(rec[i].u, rec[i].v);
        if (rec[i].k == 2) add_edge(rec[i].v, rec[i].u);
    }
    spfa1();

    idx = 0;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; ++ i) {
        add_edge(rec[i].v, rec[i].u);
        if (rec[i].k == 2) add_edge(rec[i].u, rec[i].v);
    }
    spfa2();

    int res = 0;
    for (int i = 1; i <= n; ++ i)
        res = max(res, s[i] - b[i]);
    printf("%d", res);
    return 0;
}