P1073 [NOIP2009 提高组] 最优贸易 （最短路spfa）

本题就是在一条1-n的路径上找p，q（先经过p），使得q-p最大。

考虑建正反图，正图上求出d[x]，表示1-x的路径经过的节点最小值，反图上则从n开始求出f[x]，x-n的最大值，最后枚举断点i，取最大的f[i]-d[i]就是答案。

基于动态规划的思想。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=1e5+10,M=1e6+10;

 4 int head[N],to[M],nxt[M],edge[M],tot;

 5 int n,m,a[N],d[N],f[N];

 6 bool v[N];

 7 queue<int> q;

 8

 9 void add(int x,int y,int z){

10     nxt[++tot]=head[x];

11     head[x]=tot;

12     to[tot]=y;

13     edge[tot]=z;//1只能正着走，-1只能倒着走，2正反都可以

14 }

15

16 void spfa(int *d,int st,int z){

17     d[st]=a[st];

18     q.push(st);v[st]=true;

19     while(!q.empty()){

20         int x=q.front();

21         q.pop();v[x]=false;

22         for(int i=head[x];i;i=nxt[i]){

23             if(edge[i]==z||edge[i]==2){

24                 int y=to[i];

25                 int val=z==1?min(d[x],a[y]):max(d[x],a[y]);

26                 if(z==1&&d[y]>val||z==-1&&d[y]<val){

27                     d[y]=val;//更新

28                     if(!v[y]) {q.push(y);v[y]=true;}

29                 }

30             }

31         }

32     }

33 }

34

35 int main(){

36     scanf("%d%d",&n,&m);

37     for(int i=1;i<=n;i++) scanf("%d",&a[i]);

38     for(int i=1;i<=m;i++){

39         int x,y,z;

40         scanf("%d%d%d",&x,&y,&z);

41         add(x,y,z);

42         add(y,x,z==1?-1:z);

43     }

44     memset(d,0x3f,sizeof(d));

45     spfa(d,1,1); // 从1出发求前缀min（d），只有1和2的边可以用

46     memset(f,0xcf/*负无穷*/,sizeof(f));

47     spfa(f,n,-1);// 从n出发倒着求后缀max（d），只有-1和2的边可以用

48     int ans=0;

49     for(int i=1;i<=n;i++) ans=max(ans,f[i]-d[i]);

50     printf("%d\n",ans);

51 } 

P1073 [NOIP2009 提高组] 最优贸易 （最短路spfa）的相关教程结束。