题解 P1073 【最优贸易】

Object_ · 2019-10-08 21:07:26 · 题解

如果题意莫名其妙，那么莫名其妙的不是出题人的脑袋就是我们的脑袋。——zrt

个人思路：

• 注意到进行最多一次、最多能赚取和输入格式，可以考虑一下单源最短路径。 假设我们是阿龙 的话，当然会在路径上选择最便宜的地方买物品，最贵的地方售出物品。
• 如果对Dijkstra的更新方式进行修改，就可以求出从源点到每一个点购入的最便宜价格。（对Dijkstra的理解）
• 形象地说，我们如果是阿龙的话，等于尝试走到每个点，并看从源点到每个点时，能购入的最便宜价格。
• 到这里，就有一个小技巧了。既然求得购入价格可以正着走，那么是否求售出价格可以反着走呢？
• 答案是可以的。
• 最终，进行两次Dijkstra，再枚举ans=max(售出价格[i]-购入价格[i])即可求出答案。注意，第二次Dijkstra要求进行在反图上。

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int MAXN=1000010,MAXM=1000010;
int n;
struct Edge_Low{
    int from,to,nxt;
}e_Low[MAXM];
int head_Low[MAXN],edgeCnt_Low=0;
void addEdge_Low(int u,int v){
    e_Low[++edgeCnt_Low].from=u;
    e_Low[edgeCnt_Low].to=v;
    e_Low[edgeCnt_Low].nxt=head_Low[u];
    head_Low[u]=edgeCnt_Low;
}
int price[MAXN];//各个点的价格 
const int INF=2100000000;
struct Node{
    int nowPoint,nowValue;
    bool operator <(const Node &a)const{
        return a.nowValue<nowValue;
    }
};
int s_Low;
int dis_Low[MAXN];
void dijkstra_Low(){//收购尽量低价 
    for(int i=1;i<=n;i++)dis_Low[i]=INF;
    priority_queue<Node> q;
    q.push(Node{s_Low,price[s_Low]});dis_Low[s_Low]=price[s_Low];
    while(!q.empty()){
        Node nowNode=q.top();q.pop();
        int nowPoint=nowNode.nowPoint,nowValue=nowNode.nowValue;
        if(dis_Low[nowPoint]!=nowValue)continue;
        for(int i=head_Low[nowPoint];i;i=e_Low[i].nxt){
            int nowV=e_Low[i].to;
            if(dis_Low[nowV]>dis_Low[nowPoint]){
                dis_Low[nowV]=min(dis_Low[nowPoint],price[nowV]);
                q.push(Node{nowV,dis_Low[nowV]});
            }
        }
    }
}
struct Edge_High{
    int from,to,nxt;
}e_High[MAXM];
int head_High[MAXN],edgeCnt_High=0;
void addEdge_High(int u,int v){
    e_High[++edgeCnt_High].from=u;
    e_High[edgeCnt_High].to=v;
    e_High[edgeCnt_High].nxt=head_High[u];
    head_High[u]=edgeCnt_High;
}
int s_High;
int dis_High[MAXN];
void dijkstra_High(){//售出尽量高价 
    for(int i=1;i<=n;i++)dis_High[i]=-INF;
    priority_queue<Node> q;
    q.push(Node{s_High,price[s_High]});dis_High[s_High]=price[s_High];
    while(!q.empty()){
        Node nowNode=q.top();q.pop();
        int nowPoint=nowNode.nowPoint,nowValue=nowNode.nowValue;
        if(dis_High[nowPoint]!=nowValue)continue;
        for(int i=head_High[nowPoint];i;i=e_High[i].nxt){
            int nowV=e_High[i].to;
            if(dis_High[nowV]<dis_High[nowPoint]){
                dis_High[nowV]=max(dis_High[nowPoint],price[nowV]);
                q.push(Node{nowV,dis_High[nowV]});
            }
        }
    }
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    s_Low=1,s_High=n;
    for(int i=1;i<=n;i++)scanf("%d",&price[i]);
    for(int i=1;i<=m;i++){
        int u,v,z;
        scanf("%d%d%d",&u,&v,&z);
        addEdge_Low(u,v);
        addEdge_High(v,u);
        if(z==2){
            addEdge_Low(v,u);
            addEdge_High(u,v);
        }
    }
    dijkstra_Low();
    dijkstra_High();
    int ans=-INF;
    for(int i=1;i<=n;i++)ans=max(ans,dis_High[i]-dis_Low[i]);
    printf("%d\n",ans);
    return 0;
}