本文共 4312 字，大约阅读时间需要 14 分钟。

 描述

C 国有 n 个大城市和 m 条道路，每条道路连接这 n 个城市中的某两个城市。任意两个

城市之间最多只有一条道路直接相连。这 m 条道路中有一部分为单向通行的道路，一部分

为双向通行的道路，双向通行的道路在统计条数时也计为 1 条。 

C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价

格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。 

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息

之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设 C 国 n 个城

市的标号从 1~ n，阿龙决定从 1 号城市出发，并最终在 n 号城市结束自己的旅行。在旅游的

过程中，任何城市可以重复经过多次，但不要求经过所有 n 个城市。阿龙通过这样的贸易方

式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另

一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游，他决定

这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。 

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

为单向通行，双向箭头表示这条道路为双向通行。 

假设 1~n 号城市的水晶球价格分别为 4，3，5，6，1。 

阿龙可以选择如下一条线路：1->2->3->5，并在 2 号城市以 3 的价格买入水晶球，在 3

号城市以 5的价格卖出水晶球，赚取的旅费数为 2。 

阿龙也可以选择如下一条线路 1->4->5->4->5，并在第 1 次到达 5 号城市时以 1 的价格

买入水晶球，在第 2 次到达 4 号城市时以 6 的价格卖出水晶球，赚取的旅费数为 5。

现在给出 n个城市的水晶球价格，m条道路的信息（每条道路所连接的两个城市的编号

以及该条道路的通行情况） 。请你告诉阿龙，他最多能赚取多少旅费。

想着学学Tarjan吧 于是写了个缩点+DP

然后喜闻乐见的爆0了

哈哈哈哈哈哈哈哈

不作死就不会死！！！

tarjan写的没错 错在dp了

一开始丧心病狂的从1递推 每一个点取最大值

后来发现必须停到n

也就是说必须做完交易后能走到n

也就是说 连反向边 可以从n走到交易点

所以就倒着DP啦。。。。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int lim=100011;struct self{int x,y;}s[lim*10],k[lim*10];int firsts[lim*10],nxts[lim*10];int firstk[lim*10],nxtk[lim*10];int ss,kk;int w[lim];int scc[lim],pre[lim],low[lim],maxv[lim],minv[lim];int m,n,a,b,c,sccnt,dfstime,x,y,z;stack
         
          S;void tarjan(int i){ dfstime++; pre[i]=low[i]=dfstime; S.push(i); for(int e=firsts[i];e!=-1;e=nxts[e]) { if(!pre[s[e].y]) { tarjan(s[e].y); low[i]=min(low[i],low[s[e].y]); } else if(!scc[s[e].y]) low[i]=min(low[i],pre[s[e].y]); } if(low[i]==pre[i]) { sccnt++; for(;;) { int x=S.top();S.pop(); scc[x]=sccnt; maxv[sccnt]=max(w[x],maxv[sccnt]); if(minv[sccnt]==0)minv[sccnt]=w[x];else minv[sccnt]=min(w[x],minv[sccnt]); if(x==i)break; } }}void makesides(int x,int y){ ss++;s[ss].x=x;s[ss].y=y; nxts[ss]=firsts[x]; firsts[x]=ss;}void makesidek(int x,int y){ kk++;k[kk].x=x;k[kk].y=y; nxtk[kk]=firstk[x]; firstk[x]=kk;}int f[lim],ans;int findmin(int i){ if(f[i]!=-1)return f[i]; f[i]=minv[i]; for(int e=firstk[i];e!=-1;e=nxtk[e]) f[i]=min(f[i],findmin(k[e].y)); ans=max(ans,maxv[i]-f[i]); return f[i];}int main(){ memset(firsts,-1,sizeof(firsts)); memset(nxts,-1,sizeof(nxts)); memset(firstk,-1,sizeof(firstk)); memset(nxtk,-1,sizeof(nxtk)); scanf("%d%d",&m,&c); for(a=1;a<=m;a++)scanf("%d",&w[a]); for(a=1;a<=c;a++) { scanf("%d%d%d",&x,&y,&z); makesides(x,y); if(z==2)makesides(y,x); } for(a=1;a<=m;a++)if(!pre[a])tarjan(a); for(a=1;a<=m;a++) for(int e=firsts[a];e!=-1;e=nxts[e]) if(scc[a]!=scc[s[e].y]) makesidek(scc[s[e].y],scc[a]); memset(f,-1,sizeof(f)); findmin(scc[m]); cout<
          
           <
          
         
        
       
      
     
    
   

然后说下喜闻乐见的SPFA做法

（借用spfa的思想 更新走到每个点的最值）

Spfa可以一遍找到每个点的最大最小值

不过这个是有错误的吧 因为最后要走到n

可以从1走到i交易 但是可能从i走不到n 这时候就喜闻乐见了

不过由于数据弱 (-.-) 居然可以AC！！！

还有一个是两次spfa的

第一次从1走找最小值

第二次从n走找最大值

这个应该是不存在什么问题的吧

然后我尝试写了一下

感觉写起来还不错！

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int lim=100011;const int inf=999999999;struct self{int x,y;}s[lim*10],k[lim*10];int firsts[lim*10],nxts[lim*10];int firstk[lim*10],nxtk[lim*10];int ss,kk;int w[lim];int maxv[lim],minv[lim];int m,n,a,b,c,x,y,z,ans;void makesides(int x,int y){ ss++;s[ss].x=x;s[ss].y=y; nxts[ss]=firsts[x]; firsts[x]=ss;}void makesidek(int x,int y){ kk++;k[kk].x=x;k[kk].y=y; nxtk[kk]=firstk[x]; firstk[x]=kk;}queue
          
           q;bool inq[lim];void spfamin(){ int a; memset(inq,0,sizeof(inq)); q.push(1);inq[1]=1; for(a=1;a<=m;a++)minv[a]=inf; minv[1]=w[1]; while(!q.empty()) { int u=q.front();q.pop(); for(int e=firsts[u];e!=-1;e=nxts[e]) if(minv[s[e].y]>minv[u]) { minv[s[e].y]=min(minv[u],w[s[e].y]); if(!inq[s[e].y]) { inq[s[e].y]=1; q.push(s[e].y); } } }}void spfamax(){ int a; memset(inq,0,sizeof(inq)); q.push(m);inq[m]=1; for(a=1;a<=m;a++)maxv[a]=-inf; maxv[m]=w[m]; while(!q.empty()) { int u=q.front();q.pop(); for(int e=firstk[u];e!=-1;e=nxtk[e]) if(maxv[k[e].y]
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/li412302070/article/details/14127881 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！