错误总结：

好久没有这么爽的A一道题了，这个爽代表着无数次Debug和最后的恍然大悟，然后AC。很有成就感的说，比作数学题爽得多……

首先总结一下最近写图论的时候犯的一些小错误：

1.更新a[i].point=a[i].point，说白了就是 j 打成 i ……

2.没有考虑到不去赋初值对程序的影响

3.数组名打错……比如Link1打成Link什么的……

4.两个链表运用的时候a，b搞混

5.没有小小的证明就开始乱搞，比如这道题

NOIP2009最佳贸易

题目描述：

C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。

C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。商人century来到 C 国旅游。当他从strork处得知同一种商品在不同城市的价格可能会不同这一信息

之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城市的标号从 1~ n，century决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。century通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——AWP，并在之后经过的另一个城市卖出这个AWP，用赚取的差价当做旅费。由于century主要是来C国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

假设 C 国有 5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

输入：

第一行包含 2 个正整数 n 和 m，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。

接下来 m 行，每行有 3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果 z=1，
表示这条道路是城市 x 到城市 y 之间的单向道路；如果 z=2，表示这条道路为城市 x 和城市y 之间的双向道路。

输出：

输出共 1 行，包含 1 个整数，表示最多能赚取的旅费。如果没有进行贸易，
则输出 0。

题解：

这道题的思路就是首先绕着这张图跑一便，首先要保证你买水晶球的点是可以从1号城市到达的，其次是保证你能买了水晶球能够到n号城市，卖水晶球也是同样的道理……所以说，你需要找到所有能从1号城市到达且能回到n号城市，这样的点可以被作为买卖点。

然后用一个一维数组，存下 The_max[i] 和 The_min[i] ，分别表示在i点之前能买到最便宜的水晶球 The_min[i] 和在i点之后能卖出的最贵水晶球 The_max[i] 。最后 The_max[i]-The_min[i] 就可以找到在i点之前购买，在i点之后卖出可以获得的最大利润。

开始我是用SPFA写的，但是后来超时，原因就可能是找最大解的时候一个二重循环，且现在想想那个二重循环还是不可靠的，毕竟连买入点和卖出点都不知道在不在一条路上就算答案，RP爆发的是A掉了一半的分数，剩下不是WA就是TLE。

后来听同学的话，重新写了一遍，使用BFS来遍历每一个城市，能够满足的标上true，最后在计算答案。比较麻烦的其实就是 The_max[i] 和 The_min[i] 的处理上，这两个处理是根据自己上一个节点来处理的，如果上一个节的 The_max[i] 和 The_min[i] 比自己的小/大，那么就更新自己 The_max[i] 和 The_min[i] ，否则就将上一个节点的 The_max[i] 和 The_min[i] 更新自己。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct Edge
{
    int point;
    int next;
};
Edge a[1000001],b[1000001];
int n,m,x,y,z,ans=0,Prize[100001];
int Link1[100001],Link2[100001],List[100001];
int The_max[100001],The_min[100001];
bool Ask[100001],First[100001],Last[100001];
void BFS_First()
{
    memset(Ask,true,sizeof(Ask));
    int tail=1;
    List[1]=1;
    Ask[List[1]]=false;
    First[List[1]]=true;
    The_min[List[1]]=Prize[List[1]];
    for(int i=1;i<=tail;i++)
    {
        for(int j=Link1[List[i]];j!=0;j=a[j].next)
        {
            if(Prize[a[j].point]<The_min[List[i]])
            The_min[a[j].point]=Prize[a[j].point];
            else The_min[a[j].point]=The_min[List[i]];
            if(Ask[a[j].point]==false) continue;
            else
            {
                Ask[a[j].point]=false;
                First[a[j].point]=true;
                List[++tail]=a[j].point;
            }
        }
    }
}
void BFS_Last()
{
    memset(Ask,true,sizeof(Ask));
    int tail=1;
    List[1]=n;
    Ask[List[1]]=false;
    Last[List[1]]=true;
    The_max[List[1]]=Prize[List[1]];
    for(int i=1;i<=tail;i++)
    {
        for(int j=Link2[List[i]];j!=0;j=b[j].next)
        {
            if(Prize[b[j].point]>The_max[List[i]])
            The_max[b[j].point]=Prize[b[j].point];
            else The_max[b[j].point]=The_max[List[i]];
            if(Ask[b[j].point]==false) continue;
            else
            {
                Ask[b[j].point]=false;
                Last[b[j].point]=true;
                List[++tail]=b[j].point;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    memset(Link1,0,sizeof(Link1));
    memset(Link2,0,sizeof(Link2));
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>Prize[i];
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        a[++ans].point=y;
        a[ans].next=Link1[x];
        Link1[x]=ans;
        b[ans].point=x;
        b[ans].next=Link2[y];
        Link2[y]=ans;
        if(z==2)
        {
            a[++ans].point=x;
            a[ans].next=Link1[y];
            Link1[y]=ans;
            b[ans].point=y;
            b[ans].next=Link2[x];
            Link2[x]=ans;
        }
    }
    BFS_First();
    BFS_Last();
    ans=0;
    for(int i=1;i<=n;i++)
    if(First[i]==true&&Last[i]==true)
    ans=max(ans,The_max[i]-The_min[i]);
    cout<<ans<<endl;
    return 0;
}