P1073 [NOIP2009 提高组] 最优贸易

题目描述：

n个城市，m条边，一部分是单向边，一部分是双向边，每个城市的水晶球的价格不一定相同，你可以在任意一个城市购买一个水晶球，再任意一个城市卖出，以此来赚取差价，但你只能进行一次这样的操作，且必须从1号点出发，最终要到达n号点，n个城市可以去任意次，问能赚取的最大的差价是多少

思路1:记忆化搜索

我们必须从1号点出发，到达n号点，我们可以找一个分界点i，在这个分界点之前，我们取其中1号点能到达的最小的值，在这个分界点之后再取能到达n的最大的值，做差求最大值

对于最小值，我们可以考虑记忆化搜索

void dfs_minx(int x, int p){
 if(minx[x] <= p)return;//如果已经小于当前的最小值就返回
 p = min(p, tr[x]);//更新最小值
 minx[x] = p;
 for(auto y : g1[x]){
     dfs_minx(y, p);//接着更新其他的点
 }
}

对于最大值也是类似，不过如何满足从i到n?我们只需要反向见图，然后对n进行dfs即可

void dfs_maxn(int x, int p){
 if(p <= maxn[x])return;
 p = max(p, tr[x]);
 maxn[x] = p;
 for(auto y : g2[x]){
     dfs_maxn(y, p);
 }
}

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 300000 + 50
int n, m;
int a, b, c;
int tr[MAX];
vector<int>g1[MAX];
vector<int>g2[MAX];

int minx[MAX];
int maxn[MAX];

void dfs_minx(int x, int p){
    if(minx[x] <= p)return;
    p = min(p, tr[x]);
    minx[x] = p;
    for(auto y : g1[x]){
        dfs_minx(y, p);
    }
}

void dfs_maxn(int x, int p){
    if(p <= maxn[x])return;
    p = max(p, tr[x]);
    maxn[x] = p;
    for(auto y : g2[x]){
        dfs_maxn(y, p);
    }
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    for(int i = 1; i <= n; ++i){
        minx[i] = inf;
        maxn[i] = -inf;
    }
    for(int i = 1; i <= m; ++i){
        cin >> a >> b >> c;
        if(c == 1){
            g1[a].push_back(b);
            g2[b].push_back(a);
        }
        else {
            g1[a].push_back(b);
            g2[b].push_back(a);
            g1[b].push_back(a);
            g2[a].push_back(b);
        }
    }
    dfs_minx(1, tr[1]);
    dfs_maxn(n, tr[n]);
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        ans = max(ans, maxn[i] - minx[i]);
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}

思路2:分层图最短路

建三层，层内的边的权值为0，表示不买不卖时起点可以任意，第一层和第二层之间的边权值是负数，表示买进水晶球，第二层和第三层之间的边的权值是正数，表示卖出水晶球，然后跑SPFA求最大值即可

需要注意的是数组范围

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 300000 + 50
int n, m;
int val[MAX];

int tot;
int head[MAX];
struct ran{
    int to, nex, val;
}tr[1500050];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

bool vis[MAX];
int dis[MAX];
void SPFA(){
    queue<int>q;
    q.push(1);vis[1] = 1;
    mem(dis, -inf);dis[1] = 0;
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] < dis[u] + tr[i].val){
                dis[v] = dis[u] + tr[i].val;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    cout << dis[3 * n] << endl;
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> val[i];
        add(i, i + n, -val[i]);
        add(i + n, i + 2 * n, val[i]);
    }
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        add(a, b, 0);
        add(a + n, b + n, 0);
        add(a + 2 * n, b + 2 * n, 0);
        if(c == 2){
            add(b, a, 0);
            add(b + n, a + n, 0);
            add(b + 2 * n, a + 2 * n, 0);
        }
    }
    SPFA();
}


int main(){
    io;
    work();
    return 0;
}

思路3:两次SPFA

思路和第一种比较类似，不过第一种写的是记忆化搜索来确定从1开始到i的最小值，和从i到n的最大值，这里用的是SPFA来确定，只需要将SPFA中的松弛操作改成比较大小即可

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

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

#define MAX 300000 + 50
int n, m;
int tr[MAX];
vector<int>v1[MAX], v2[MAX];
int minx[MAX], maxn[MAX];
bool vis[MAX];
void SPFA1(){
    queue<int>q;q.push(1);
    mem(minx, inf);minx[1] = tr[1];
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(auto v : v1[u]){
            if(minx[v] > min(minx[u] , tr[v])){
                minx[v] = min(minx[u] , tr[v]);
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}
void SPFA2(){
    queue<int>q;q.push(n);
    for(int i = 1; i <= n; ++i)maxn[i] = -inf;
    mem(vis, 0);
    maxn[n] = tr[n];
    while (!q.empty()) {
        int u = q.front();q.pop();vis[u] = 0;
        for(auto v : v2[u]){
            if(maxn[v] < max(maxn[u], tr[v])){
                maxn[v] = max(maxn[u], tr[v]);
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

void work(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
    }
    for(int i = 1, a, b, c; i <= m; ++i){
        cin >> a >> b >> c;
        v1[a].push_back(b);
        v2[b].push_back(a);
        if(c == 2){
            v1[b].push_back(a);
            v2[a].push_back(b);
        }
    }
    SPFA1();
    SPFA2();
    int ans = 0;
    for(int i = 1; i <= n; ++i){
        ans = max(ans, maxn[i] - minx[i]);
    }
    cout << ans << endl;
}

int main(){
    io;
    work();
    return 0;
}