NOIP2009 最优贸易

思路：
这道题就是让你在图上找两个点，在第一个点买入，在第二个点卖出，而且第一个点必须在路中第二个点之前的。在网上有一种写法是两遍广搜然后找最大和最小，然后Blablabla。
由于我这题的写法有点奇怪（？），我就来介绍一下。
首先介绍一个叫做差分序列的东西。
如果当前序列为 Ai,Ai+1,Ai+2,Ai+3,……
那么我们把序列变成 Ai+1-Ai,Ai+2-Ai+1的形式，通过前缀和，就会得到当前的点值，乍一看是没用的，不过区间加减是很好用的。例如：NOIP借教室这一题。
我借用了差分的思想，对这个图的边变成了两点权值差，当我们走过一条路时，便会得到终点和起点的权值差。
于是我们可以广搜枚举路，类似spfa的思想。但是由于我们是单纯枚举路，还有可能得到一条不会到达终点的路，这时候就先用反图判一下合法的点。PS：由于有环，我们就限制一个点只能被最多入两次。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stack>
#define N 100005
struct aa{
    int p,len,next;
}da[N*2],dx[N*2];
std::queue <int>q; 
int dist[N],dd,tou[N],n,m,val[N],to[N],xx;
bool inq[N];
int in[N];
void add(int u,int v,int len){
    da[++dd].p=v;da[dd].next=tou[u];tou[u]=dd;da[dd].len=len;
}
void ad(int u,int v){
    dx[++xx].p=v;dx[xx].next=to[u];to[u]=xx;
}
void spfa(){
    q.push(1);
    ++in[1];
    while (!q.empty()){
        int u=q.front();q.pop();
        if (in[u]>2)continue;
        for (int i=tou[u];i;i=da[i].next){
            int v=da[i].p;
            if (dist[u]+da[i].len>dist[v])dist[v]=dist[u]+da[i].len;
            if (inq[v])q.push(v);++in[v];
        }
    }
}
void bfs(int x){
    inq[x]=1;
    q.push(x);
    while (!q.empty()){
        int u=q.front();
        q.pop();
        for (int i=to[u];i;i=dx[i].next){
            int v=dx[i].p;
            if (!inq[v]){
                q.push(v);
                inq[v]=1;
            }
        } 
    }
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("c1413.in","r",stdin);
    freopen("c1413.out","w",stdout);
    #endif 
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)scanf("%d",&val[i]);
    for (int i=1;i<=m;i++){
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        if (z==1)add(x,y,val[y]-val[x]),ad(y,x);
        else {
            add(x,y,val[y]-val[x]);
            add(y,x,val[x]-val[y]);
            ad(x,y);
            ad(y,x);
        }
    } 
    bfs(n);
    spfa();
    int max=-100000;
    for (int i=1;i<=n;i++)max=std::max(max,dist[i]); 
    printf("%d",max);
    return 0;
}

今天的文章NOIP2009 最优贸易分享到此就结束了，感谢您的阅读。