P1073 最优贸易

[最优贸易]

• 有费用的路径问题可以考虑最短路
• 分为三个阶段，起点到购买点，购买点到售卖点，售卖点到终点
• 使用分层图思想，将原图复制为三份应对三个阶段
• 从第一层图到第二层图对应购买，对于每个点从第一层到第二层连边，权值为在这个点购买的费用
• 从第二层图到第三层图对应售卖，同理连边，权值为负的费用
• 由于移动不需要费用，三层图内部的边权为0
• 之后求出来的最短路，层内部的对应移动，跨层的对应购买或者销售操作

• 建三层图(核心思想)
• 起点层
• 购买层
• 出售层
• 也就是说有3n个点，我们立3n+1点为最终点，当然通向它的权值是零，与它相连的是n(不买卖直接走)和3n(卖卖后)
  

• 方法一：Dijkstra + 最小堆优化
• 立起点层到购买层权值为正数
• 立购买层到出售层权值为负数
• 意为总共付出的费用(付出负数即为赚钱)
• 方法二：Dijkstra + 最大堆优化
• 立起点层到购买层权值为负数
• 立购买层到出售层权值为正数
• 意为总共得到的费用

• 最终答案在dist[3 * n + 1]
• 法一输出abs(dist[3 * n + 1])
• 法二输出dist[3 * n + 1]

Dijkstra + 最小堆 代码

#include <bits/stdc++.h>

#define pr pair<int, int>
#define mk make_pair

using namespace std;

const int N = 3e5 + 1;

struct Edge{
    int v,w,nxt;
}edge[N << 2];

int n,m,top;
int cost[N],head[N],dist[N]; 

void addedge(int u, int v, int w){
    edge[++top].v = v;
    edge[top].w = w;
    edge[top].nxt = head[u];
    head[u] = top;
}

void add(int x, int y){
    addedge(x, y, 0), addedge(n + x, n + y, 0), addedge(2 * n + x, 2 * n + y, 0);
    addedge(x, n + y, cost[y]), addedge(n + x, 2 * n + y, -cost[y]);
}

priority_queue<pr, vector<pr>, greater<pr> > q; 
void Dijkstra(){
    for(int i = 1; i <= n; ++i) dist[i] = dist[n + i] = dist[2 * n + i] = 1e9;
    dist[1] = 0;
    q.push(mk(dist[1], 1)); 
    while(!q.empty()){
        int u = q.top().second;
        int d = q.top().first; q.pop();
        if(d > dist[u]) continue;
        for(int i = head[u]; i; i = edge[i].nxt){
            int v = edge[i].v;
            int w = edge[i].w;
            if(dist[u] + w < dist[v]) dist[v] = dist[u] + w, q.push(mk(dist[v], v));
        }
    }
    cout << abs(dist[3 * n + 1]);
}

int main(){
    cin >> n >> m;
    for(int i = 1, x; i <= n; ++i)
        cin >> x, 
            cost[i] = cost[n + i] = cost[2 * n + i] = x;
    for(int i = 1, x, y, z; i <= m; ++i){
        cin >> x >> y >> z;
        add(x, y);  
        if(z == 2) add(y, x);
    }
    addedge(n, 3 * n + 1, 0); //不买卖，直接走 
    addedge(3 * n, 3 * n + 1, 0); //终点是3 * n + 1 
    Dijkstra();
    return 0;   
}

P1073 最优贸易

原文：https://www.cnblogs.com/Adventurer-H/p/11281701.html