题解【洛谷P1073】[NOIP2009]最优贸易

题面

考虑从集合的角度思考这一个问题。

首先给出我对于“分割点”的定义：即在这个城市之前买入，在这个城市之后卖出，可以在这个城市买入或卖出。

我们发现，如果我们按照哪一个城市作为分割点，那么最优解就会被包含在我们讨论的情况中。

我们设当前枚举到的分割点是 (k)，(dmin_k) 表示在 (1sim k) 买入的最小值，(dmax_k) 表示在 (ksim n) 卖出的最大值。

那么我们的答案就是 (max{max_{1leq ileq n}{dmax_i-dmin_i}, 0})。

注意在这一题中，使用 Dijkstra 求最短路是错误的。因为使用 Dijkstra 算法的必要条件就是 每一次取出堆的元素都不会再被更新，而在此题中，任何城市可以重复经过多次 ，所以我们取出堆的元素是有可能会被更新的。因此我们只可以使用 SPFA 算法。

我们可以建出一个反图，然后正反分别跑一遍 SPFA，求出 (dmin_i) 和 (dmax_i) 的值。最后求出答案即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 100003, M = 2000003;

int n, m;
int w[N];
int heads[N], heade[N], ver[M], nxt[M], tot;
int dmin[N], dmax[N];
int vis[N];

inline void add(int head[], int u, int v)
{
    ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}

inline void SPFA(int head[], int dist[], int ty)
{
    queue <int> q;
    if (ty == 0) 
    {
        memset(dist, 0x3f, sizeof dmin);
        dist[1] = w[1];
        q.push(1);
    }
    else 
    {
        memset(dist, 0xcf, sizeof dmax);
        dist[n] = w[n];
        q.push(n);
    }
    memset(vis, 0, sizeof vis);
    while (!q.empty())
    {
        int u = q.front(); q.pop();
        vis[u] = 0;
        for (int i = head[u]; i; i = nxt[i])
        {
            int v = ver[i];
            if (ty == 0)
            {    
                if (dist[v] > min(dist[u], w[v]))
                {
                    dist[v] = min(dist[u], w[v]);
                    if (!vis[v])
                        vis[v] = 1, q.push(v);
                }
            }
            else
            {
                if (dist[v] < max(dist[u], w[v]))
                {
                    dist[v] = max(dist[u], w[v]);
                    if (!vis[v])
                        vis[v] = 1, q.push(v);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i+=1) scanf("%d", &w[i]);
    for (int i = 1; i <= m; i+=1)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(heads, u, v), add(heade, v, u); //建反图
        if (w == 2) add(heads, v, u), add(heade, u, v); //双向边
    }
    SPFA(heads, dmin, 0); //正着求出 dmin
    SPFA(heade, dmax, 1); //反着求出 dmax
    int ans = 0;
    for (int i = 1; i <= n; i+=1)
        ans = max(ans, dmax[i] - dmin[i]); //取最大值
    printf("%d
", ans);
    return 0;
}