NOIP2009T3最优贸易（Dfs + spfa）

洛谷传送门

看到这个题，原本想先从后往前dfs，求出能到终点的点，再在这些点里从前往后spfa，用一条边上的两个城市的商品价格的差来作边权，实施过后，发现图中既有负边权，又有回路，以及各种奇奇怪怪的东西。说实话我连样例都没过，然后提交一下试试，得了10分。

然而我发现，要求赚最多钱，就是到那个点的路径上的最大价格 最小价格。

两边dfs——

最小价格可以从前往后搜来算。

最大价格可以从后往前搜来算。

最后枚举一边所有点maxx minn的最大值就好。

说出来你可能不信，我是看的题解。

——代码

#include <cstdio> #include <cstring> #include <queue> #include <iostream> using namespace std; int n, m, cnt1, cnt2, ans; int a[100001], next1[1000001], to1[1000001], head1[100001], next2[1000001], to2[1000001], head2[100001], maxx[100001], minn[100001]; inline void add1(int x, int y) inline void add2(int x, int y) inline void dfs2(int u, int k) } inline void dfs1(int u, int k) } int main() for(i = 1; i <= m; i++) else } dfs1(1, a[1]); dfs2(n, a[n]); for(i = 1; i <= n; i++) ans = max(ans, maxx[i] minn[i]); printf("%d", ans); return 0; }
View Code

其中dfs不用设置vis来记录是否被访问过，因为有双向道路，所以走到一个点有可能会返回来，所以进行深搜的判断标准是目标点（姑且这么说吧）的最大最小值小于或大于当前点的最大最小值。这样即使走到后面的点，发现前面的点需要修改，也可以改回去。

也可以用 spfa ，改变一下松弛操作，dis 数组表示到当前点的路径上买入的最小值，最后统计一遍就行。

——代码

1 #include <queue> 2 #include <cstdio> 3 #include <cstring> 4 #include <iostream> 5 6 using namespace std; 7 8 const int MAXN = 200001; 9 int n, m, cnt, cnt1, ans; 10 int a[MAXN], head[MAXN], to[MAXN], next[MAXN], head1[MAXN], to1[MAXN], next1[MAXN], dis[MAXN]; 11 bool b[MAXN], vis[MAXN]; 12 queue <int> q; 13 14 inline void add(int x, int y) 15 20 21 inline void add1(int x, int y) 22 27 28 inline void dfs(int u) 29 37 } 38 39 inline void spfa(int u) 40 61 } 62 } } 64 } 65 66 int main() 67 81 else 82 88 } 89 dfs(n); 90 spfa(1); 91 for(i = 1; i <= n; i++) 92 if(b[i]) 93 ans = max(ans, a[i] dis[i]); 94 printf("%d", ans); 95 return 0; 96 }
View Code

上一篇：飞行员配对方案问题（匈牙利算法+sort）

下一篇：[洛谷P2580]于是他错误的点名开始了（Trie树）

---

spfa dfs 最短路