最优贸易解题报告

本文主要是介绍最优贸易解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

----------------------------最优贸易是一个n=10^5级的稀疏图，求max{0,w[j]-w[i]}(g[1][i]&&g[i][j]&&g[j][n]).----------------------------
一、SPFA的功能与理解，不能仅仅局限于求最短路，而可以是图中某点到图中所有点的某种关系。比如说本题中可以用来求某点到1的所有路径中的Wmax。
二、DFS解法给我们的启示：
    ①求可到n的点的集合与1可到的点的集合的交集，实际只需要预先一遍DFS将不可到n的点都删掉即可，反之亦成立。
    ②在有环图中，只需将每个点只可经过最多一次改为每个点只可经过最多两次即可。
    ③可以以前驱和后继划分阶段，将DP与图论结合起来。（记忆化搜索）
三、 SPFA解法给我们的启示：MITM思想以及SPFA的灵活运用。
四、SPFA+DP解法给我们的启示：
    类似背包DP中，若j<a[i]，仍然需要有f[i][j]=f[i-1][j]这种状态的携带。 
    使用纯正面思想解这道题，一个保存了两个变量的类DP·SPFA，保存1到每个点路径的最小值mn，1到每个点可赚旅费最大值mx。
                                                        mn[i]=min(mn[j],w[i])j∈{x|x=pred(i)}
                                                        mx[i]=max(w[i]-mn[i],mx[j])j∈{x|x=pred(i)}
    ①其正确性成立的原因是：mn[i]对mx[i]的影响是单向的。
    ②在对mx[i]的转移中，mx[j]的加入使得状态得以携带和优化，这也是DP的一个常见写法，但我似乎没学会。。还没有深刻理解。。这样使得mx[i]保存的确确实实是当前能求出的最优的mx[i].
    ③在对mx[i]的SPFA中，实际上每个1能到达的点都是应至少被遍历一遍的，所以其赋值应为mx[i]=-1(1<i<=n),mx[1]=0，而不是mx[i]=0(0<i<=n)，这种奇怪而简洁而高效的编程技巧也是我们在平时需要思考、总结、学习和积累的。
五、对于fread、inline（虽然在NOIP和NOI中用不到。。）、vector、map等实用的东西以后应勤加使用，多多练习，多熟悉。。。尤其是fread在这种输入数据特别多的时候还是很有用的，与template结合的代码也是很简洁的。
六、 练习对next数组的使用，虽然其作用起初是替代邻接表，但是我们发现其在代码复杂度上的优势是相当高的，而空间开销的劣势在竞赛中是完全可以忽略不计的。
            综上，通过做最优贸易。。通过看题解。。我主要懂得了如何变化应用SPFA。。以及其他一些琐碎而重要的事情

这篇关于最优贸易解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---