题解 P1073 【最优贸易】

· · 题解

安利一发自己的博客：http://www.cnblogs.com/OIerShawnZhou/

（我平常写的题解都会往博客里发，欢迎各位大佬前来拍砖）

坑点略多就是了。。有些地方必须用奇怪的写法才可以，否则绝对爆0。。。。

这题题意要求我们求出能赚取的最大差价。说到差价很好想了，肯定是卖出价-买入价=差价。

题目规定了从点1出发到点n，我的做法是，从起点正向跑一次spfa，可以求出所有的买入价的最小值。然后从终点反向跑一次spfa，可以求出所有卖出价的最大值。最后维护一下最大差价便是答案。

稍微想一下便能发现这个算法正确性是显然的。至少我这么认为。

建图的时候有单向边有双向边，判断一下就好了。

（我一直弄不明白判断为啥if不行swicth可以。。。）

参考代码：

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#define maxn 500001
#define INF 0x7fffffff / 2
#define debug cout << "OK" << endl;
using namespace std;
struct Edge{
    int from,to,dis;
};
int ball_val[maxn];
int n,m,u,v,dir,w;
int ans = -INF;
Edge pos_edge[maxn];
Edge nag_edge[maxn];
int pos_head[maxn],pos_tot=0;
int nag_head[maxn],nag_tot = 0;
int pos_dis[maxn];
int nag_dis[maxn];
bool inq[maxn];
int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-')
        flag = true;
    else
        num = c - '0';
    while (isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
void pos_add_edge(int from,int to,int dis){
    pos_edge[++pos_tot].from=pos_head[from];
    pos_edge[pos_tot].to = to;
    pos_edge[pos_tot].dis = dis;
    pos_head[from] = pos_tot;
}

void nag_add_edge(int from,int to,int dis){
    nag_edge[++nag_tot].from=nag_head[from];
    nag_edge[nag_tot].to = to;
    nag_edge[nag_tot].dis = dis;
    nag_head[from] = nag_tot;
}
void pos_spfa(int s){
    queue<int> q;
    memset(inq,false,sizeof(inq));
    q.push(s);
    inq[s] = true;
    pos_dis[1] = ball_val[1];
    for (register int i=2;i<=m;i++)
        pos_dis[i] = INF;
    while (!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (register int i=pos_head[u];i!=0;i=pos_edge[i].from){
            int v = pos_edge[i].to;
            int w = pos_edge[i].dis;
            if (pos_dis[v]>w || pos_dis[v]<pos_dis[u]){
                pos_dis[v] = min(w,pos_dis[u]);
                if (!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
}
void nag_spfa(int s){
    queue<int> q;
    memset(inq,false,sizeof(inq));
    q.push(s);
    inq[s] = true;
    nag_dis[m] = ball_val[m];    
    for (register int i=1;i<m;i++)
        nag_dis[i] = -INF;

    while (!q.empty()){
        int u = q.front();
        q.pop();
        inq[u] = false;
        for (register int i=nag_head[u];i!=0;i=nag_edge[i].from){
            int v = nag_edge[i].to;
            int w = nag_edge[i].dis;
            if (nag_dis[v]<w || nag_dis[v]<nag_dis[u]){
                nag_dis[v] = max(w,nag_dis[u]);
                if (!inq[v]){
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main(){
    n = read();m = read();
    for (register int i=1;i<=n;i++)
        ball_val[i] = read();
    for (int i=1;i<=m;i++){
        u =read();v = read();dir = read();
        switch(dir){
            case 1:
                pos_add_edge(u,v,ball_val[v]);
                nag_add_edge(v,u,ball_val[u]);
                break;
            case 2:
                pos_add_edge(u,v,ball_val[v]);
                nag_add_edge(v,u,ball_val[u]);
                pos_add_edge(v,u,ball_val[u]);
                nag_add_edge(u,v,ball_val[v]);
                break;
        }
    }
    pos_spfa(1);nag_spfa(n);
    for (register int i=1;i<=n;i++){
        w = nag_dis[i] - pos_dis[i];
        ans = max(ans,w);
    }    
    printf("%d",ans);
    return 0;
}