NOIP 2009 最优贸易

容易知道，商人的旅行路线一定是这样的：
1--->A--->B--->N
他在A点买入，在B点卖出，因此，容易想到下面的算法：

1、先BFS标记可以由1到达的点；
2、然后BFS标记可以到N的点；
3、对于第一步标记可达的点BFS，计算如果在这个点购买，并且可以到达终点，可以获得的最大差价（需要用到第二步的结果）；
4、输出第三步中结果的最大值即可。

不过，这种算法的效率不是很高，仅仅通过了50%的数据。因此，还需要对问题做进一步分析。
题目仅仅要我们求出商人的最大收益，并没有问A，B两点的位置，有又因为A可以到达B，所以在A->B的路径中（包括AB）一定存在一个或者几个点，满足条件：
1-->X-->N
X靠近1一侧可以低价买入，靠近N一侧可以高价卖出，我们只要把每个点两侧的最低最高价格求出来就可以了。
要实现这一点，只需要把上面BFS稍稍修改即可，即在每次扩展节点的时候比较价格，详见代码88～96行，62～70行。

代码：

C语言: 高亮代码由发芽网提供

001 #include <stdio.h>
002 #include <stdlib.h>
003 #include <string.h>
004
005 #define MXN (100000+10)
006 #define QL 10000000
007
008 typedef struct node
009 {
010     int v;
011     struct node *next;
012 }node;
013
014 long queue[QL];
015 long head,tail;
016 int price[MXN];
017 int c1[MXN] = {};
018 int cn[MXN] = {};
019 long N,M;
020 node *first[MXN];
021 node *reverse[MXN];
022
023 void enqueue(long a)
024 {
025     queue[tail] = a;
026     tail = (tail + 1) % QL;
027 }
028
029 int get_min(int a,int b)
030 {
031     if(a < b)    return a;
032     return b;
033 }
034
035 int get_max(int a,int b)
036 {
037     if(a > b)    return a;
038     return b;
039 }
040
041 long dequeue()
042 {
043     long r;
044     r = queue[head];
045     head = (head + 1) % QL;
046     return r;
047 }
048
049 void bfs1()
050 {
051     node *p;
052     long i;
053     head = tail = 0;
054     c1[1] = price[1];
055     enqueue(1);
056     while(head < tail)
057     {
058         i = dequeue();
059         for(p = first[i];p != NULL;p = p->next)
060         {
061             if(c1[i] < c1[p->v])
062             {
063                 c1[p->v] = c1[i];
064                 enqueue(p->v);
065             }
066             else if(c1[p->v] == 0)
067             {
068                 c1[p->v] = get_min(price[p->v],c1[i]);
069                 enqueue(p->v);
070             }
071         }
072     }
073 }
074
075 void bfs2()
076 {
077     node *p;
078     long i;
079     head = tail = 0;
080     cn[N] = price[N];
081     enqueue(N);
082     while(head < tail)
083     {
084         i = dequeue();
085         for(p = reverse[i];p != NULL;p = p->next)
086         {
087             if(cn[p->v] == 0)
088             {
089                 cn[p->v] = get_max(price[p->v],cn[i]);
090                 enqueue(p->v);
091             }
092             else if(cn[i] > cn[p->v])
093             {
094                 cn[p->v] = cn[i];
095                 enqueue(p->v);
096             }
097         }
098     }
099 }   
100
101 void addedge(long b,long e)
102 {
103     node *p;
104     p = malloc(sizeof(node));
105     p->v = e;
106     p->next = first[b];
107     first[b] = p;
108     //reverse adjlink,for BFS2
109     p = malloc(sizeof(node));
110     p->v = b;
111     p->next = reverse[e];
112     reverse[e] = p;
113 }
114
115 int main()
116 {
117     scanf("%ld%ld",&N,&M);
118     long i,j,k;
119     int max;
120     for(i = 1;i <= N;i ++)
121         scanf("%d",&price[i]);
122     while(M --)
123     {
124         scanf("%ld%ld%ld",&i,&j,&k);
125         if(k == 1)
126             addedge(i,j);
127         else if(k == 2)
128         {
129             addedge(i,j);
130             addedge(j,i);
131         }
132     }
133     bfs1();
134     bfs2();
135     for(i = 1,max = 0;i <= N;i ++)
136     {
137         if(cn[i] - c1[i] > max)
138             max = cn[i] - c1[i];
139     }
140     printf("%d\n",max);
141     return 0;
142 }