题解 P1073 【最优贸易】

· · 题解

2018.11.3更新

经xunzhen大佬指出错误，发现在更新过程中省略了一个关键步骤：flag[y]=0，目前已更正。欢迎各位大佬指出错误，一起探讨，进步

2019.9.30更新

加入latex，优化观感（虽然没人看）

这道题是我们刚学最短路和差分约束系统的考试题，所以想的时候直接就奔着这个方向去了。下面是本蒟蒻的思路（第一次写题解，排版太丑，还请各位神犇见谅）

1. 预处理

要跑最短路（这道题实际是最长路），首先我们要建一个图。而这道题没有边权，那么就需要我们自己来建边。因为每一个城市的水晶球有自己的价格，所以如果是从低价走到高价，我们可以赚钱，那么就建一条正边，而如果不能赚钱，那就建一条为0的边。

void addedge(int x,int y,int z){
    e[++cnt].next=h[x];
    e[cnt].to=y;
    e[cnt].value=z;
    h[x]=cnt;
}//前向星标准写法
for(int i=1;i<=n;i++) v[i]=read();
    for(int i=1;i<=m;i++){
        int a,b,c;
        a=read();
        b=read();
        c=read();
        addedge(a,b,max(0,v[b]-v[a]));//可以赚v[b]-v[a]的钱或者赚不了球
        if(c==2) addedge(b,a,max(0,v[a]-v[b]));//同上
    }

2. 核心算法（spfa）

现在图已经建好了，现在应该跑一遍最短路最长路了。而此题需要注意的是只能进行一次贸易，这也是和普通的最长路不同的地方，所以我在这里多开了一个flag数组记录是否已经进行贸易。当已经进行了贸易，也就是flag[]==1时，我们不能直接按照最短路最长路的写法（d[y]=d[x]+e[i].value),而是在d[x]和e[i].value之间做出抉择，选择最大值继承下来。这里要注意，选择了e[i].value就意味着选择了新的贸易，而此时可以看作没有卖出，flag[y]=0，而若是选择了d[x],说明是继承之前的贸易，已经卖掉（继承是为了传下去到终点），所以flag[y]=1。

3. 完美收尾

到了现在，图已经建好了，spfa也写好了，拼起来最后d[n]就是我们的答案。最后来一波完整代码。

#include<cstdio>
#include<iostream>
#include<queue>
#define inf 0x7fffffff/2
using namespace std;
inline int read(){
    char c;
    int x=0,flag=1;
    for(c=getchar();c<'0'||c>'9';c=getchar()) if(c=='-') flag=-1;
    for(;c<='9'&&c>='0';c=getchar()) x=x*10+c-'0';
    return x*flag;
}//快读
struct edge{
    int to,next,value;
};
edge e[1000005];
int n,m,v[100005],cnt,h[100005],vis[100005],flag[100005],d[100005];
void addedge(int x,int y,int z){
    e[++cnt].next=h[x];
    e[cnt].to=y;
    e[cnt].value=z;
    h[x]=cnt;
}
queue<int> q;
void Spfa(){
    for(int i=1;i<=n;i++) d[i]=-inf;
    d[1]=0;
    q.push(1);
    vis[1]=1;
    while(!q.empty()){
        int k=q.front();
        vis[k]=0;
        for(int i=h[k];i;i=e[i].next){
            int y=e[i].to;
            if(!flag[k]){
                if(d[y]<d[k]+e[i].value){
                    d[y]=d[k]+e[i].value;
                    if(!vis[y]){vis[y]=1;q.push(y);}
                    if(v[y]<v[k]) flag[y]=1;
                }
            }
            else{
                if(d[y]<d[k]){
                    d[y]=d[k];
                    if(!vis[y]){vis[y]=1;q.push(y);}
                    flag[y]=1;//继承前面的贸易，可以理解为水晶球在前面已经卖掉，没有传到这里
                }
                if(d[y]<e[i].value){
                    d[y]=e[i].value;//开始新的贸易
                    flag[y]=0;
                    if(!vis[y]){vis[y]=1;q.push(y);}
                }
            }
        }
        q.pop();
    }
}
int main(){
    n=read();
    m=read();
    for(int i=1;i<=n;i++) v[i]=read();
    for(int i=1;i<=m;i++){
        int a,b,c;
        a=read();
        b=read();
        c=read();
        addedge(a,b,max(0,v[b]-v[a]));
        if(c==2) addedge(b,a,max(0,v[a]-v[b]));
    }
    Spfa();
    cout<<d[n];
}