精品|NOIP 2009 最优贸易搜索与回溯|深度优先搜索|图论

题目描述 CC国有nn个大城市和mm条道路，每条道路连接这nn个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这mm条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为11条。
CC国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到CC国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设CC国 n 个城市的标号从1 n1n，阿龙决定从11号城市出发，并最终在nn号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有nn个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品――水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来CC国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设CC国有55个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

文章图片

假设1 n1n号城市的水晶球价格分别为4,3,5,6,14 , 3 , 5 , 6 , 1。
阿龙可以选择如下一条线路：11->22->33->55，并在22号城市以33的价格买入水晶球，在33号城市以55的价格卖出水晶球，赚取的旅费数为 2。
阿龙也可以选择如下一条线路11->44->55->44->55，并在第11次到达55号城市时以11的价格买入水晶球，在第22次到达44号城市时以66的价格卖出水晶球，赚取的旅费数为55。
现在给出nn个城市的水晶球价格，mm条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
输入输出格式输入格式：
【精品|NOIP 2009 最优贸易】
第一行包含22个正整数nn和mm，中间用一个空格隔开，分别表示城市的数目和道路的数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这 n 个城市的商品价格。
接下来mm行，每行有33个正整数x,y,zx , y , z，每两个整数之间用一个空格隔开。如果z=1z = 1，表示这条道路是城市xx到城市yy之间的单向道路；如果z=2z = 2，表示这条道路为城市xx和城市yy之间的双向道路。
输出格式：

一个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出00。
输入输出样例输入样例#1：复制

5 5 4 3 5 6 1 1 2 1 1 4 1 2 3 2 3 5 1 4 5 2

输出样例#1：复制

5

说明【数据范围】
输入数据保证11号城市可以到达nn号城市。
对于 10%的数据，1≤n≤61 ≤ n ≤ 6。
对于 30%的数据，1≤n≤1001 ≤ n ≤ 100。
对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。
对于 100%的数据，1≤n≤1000001 ≤ n ≤ 100000，1≤m≤5000001 ≤ m ≤ 500000，1≤x1 ≤ x，y≤ny ≤ n，1≤z≤21 ≤ z ≤ 2，1≤1 ≤各城市
水晶球价格≤100≤ 100。
NOIP 2009 提高组第三题

看了之后不难想到，dfs
从1开始dfs，处理出前面路径上的最小值和后面路径上的最大值，然后低进高出就ok
双向边仍然按两条边来加，但是加一个bool 变量id，记录当前边是否存在镜像边，比较方便
双向边特判，如果是双向边（程序里的id=1）就说明这个点的前一个点也可以是这个点的后一个点，这个点也可以是这个点的前一个点，只看文字可能比较晕，我画了个图写出来式子就清晰了。。。
然后大概想一下，preMin可以全部处理完，因为是递归回去的
但是nextMax恐怕不行。。。
但是对结果并没有影响
最后还要记录这个点能不能到达第n个点，实现就是程序里的Node中的yes
然后枚举所有点，找出能到的， ans=max(ans,nextMax?preMin)a n s = m a x ( a n s , n e x t M a x ? p r e M i n )
ans初值设0
当然每个点只需要dfs一遍，因为不确定的是它前面的路，而不是它后面的路，这个应该不难理解
复杂度应该是 O(n+m)O ( n + m )
下面是发在luogu上的，和这篇不完全一样，有的地方分析的更加细致（大概）：https://www.luogu.org/blog/lqyzsun/solution-p1073
顺便一提，好像可以用spfa来做，非常巧妙，但是我没有想到。。。
代码

#include #include #include #include #include #include #define For(i,l,r) for(int i=l; i<=r; ++i) #define MAXN 100010 #define MAXNN 500010 using namespace std; inline int read() { char c; bool t=0; int a=0; while((c=getchar())==' '||c=='\n'||c=='\r'); if(c=='-') { t=1; c=getchar(); } while(isdigit(c)) { a*=10; a+=(c-'0'); c=getchar(); } return a*(t?-1:1); } struct Node{ int v,preMin,nextMax,last; bool yes; }p[MAXN]; struct Edge{ int to,next; bool id; }e[MAXNN*2]; int n,m,cnt; bool vis[MAXN]; void add(int from,int to,bool id) { e[++cnt].to=to; e[cnt].next=p[from].last; p[from].last=cnt; e[cnt].id=id; } void dfs(int now,int pre) { vis[now]=1; if(pre) p[now].preMin=min(p[now].preMin,p[pre].preMin); int temp=p[now].last; while(temp) { if(!vis[e[temp].to]) dfs(e[temp].to,now); p[now].yes=(p[now].yes|p[e[temp].to].yes); p[now].nextMax=max(p[e[temp].to].nextMax,p[now].nextMax); if(e[temp].id) { p[now].preMin=min(p[now].preMin,p[e[temp].to].preMin); p[e[temp].to].nextMax=max(p[e[temp].to].nextMax,p[now].nextMax); } temp=e[temp].next; } } int main() { int tx,ty,tz,ans=0; n=read(); m=read(); p[n].yes=1; For(i,1,n) { p[i].v=read(); p[i].preMin=p[i].v; p[i].nextMax=p[i].v; } For(i,1,m) { tx=read(); ty=read(); tz=read(); if(tz==1) add(tx,ty,0); else { add(tx,ty,1); add(ty,tx,1); } } dfs(1,0); For(i,1,n) { if(p[i].yes) ans=max(ans,p[i].nextMax-p[i].preMin); } printf("%d",ans); return 0; }