09省赛acm算法参考

《09省赛acm算法参考》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、09省赛邵伯仲的算法参考1最短路径解析（1-7页）2中国剩余定理（7-11页）3有重复元素排列问题（11-12）4欧拉回路问题（13-16页）5母函数问题（17-25页）6集合划分问题（25页）7常系数线性递推矩阵乘法(26-30页)33最短路径解析最短路径（ShortestPath）是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径（source-sink），单源点的最短路径（single-source），所有点到所有点（all-pairs）以及带负边情况下的最短路径。为了简化我们的问题，设置以下几个限制：有向

2、图，无向图可以看作每条边对应两条方向相反的有向边无负环，可以想象，如果存在负环则路径值可不断减小，含负环的最短路径是NP的，暂不讨论。单源点最短路径的简单算法单源点最短路径（无负边）可以用Dijkstra算法较好的解决，其思想类似与求最小生成树（MST）的Prim算法。只是Dijkstra将优先队列的权由两点的边改为了从源点到下一点的路径：Prim:Priority=edge.weight()//从v点到w点的weightDijkstra:Priority=wt[v]+edge.weight()//从源点到w点的值，wt[v]表

3、示源点到v点的值注意，wt保存的就是Priority。类似于Prim，Dijkstra算法的复杂度主要取决于优先队列的实现，普通的Dijkstra算法能在线性时间内解决单源点无负边的最短路径问题，即复杂度为V2。采用了优先队列的数据结构后，可以在ElgdV-Elg2V之间解决问题（d表示采用d-堆）。点到点的无负边最短路径也可以用Dijkstra来解决，从源点出发，当搜索到目标点时停止搜索。十分容易理解，我就不罗嗦了。All-Pairs的最短路径问题正如大多数教材中所讲到的，求单源点无负边最短路径用Dijkstra，而求所有点最

4、短路径用Floyd。确实，我们将用到Floyd算法，但是，并不是说所有情况下Floyd都是最佳选择。对于没有学过Floyd的人来说，在掌握了Dijkstra之后遇到All-Pairs最短路径问题的第一反应可能会是：计算所有点的单源点最短路径，不就可以得到所有点的最短路径了吗。简单得描述一下算法就是执行V次Dijkstra算法，自然其复杂度在最优情况下可以是VElgdV。Floyd可以说是Warshall算法的扩展了，三个for循环便可以解决一个复杂的问题，应该说是十分经典的。从它的三层循环可以看出，它的复杂度是V3，除了在第二层

5、for中加点判断可以略微提高效率，几乎没有其他办法再减少它的复杂度。33比较两种算法，不难得出以下的结论：对于稀疏的图，采用V次Dijkstra比较出色，对于茂密的图，可以使用Floyd算法。另外，Floyd可以处理带负边的图。无环网络的最短路径问题无环网络（与DAG略微有区别）较带环网络而言，因为无环，所以边的正负是无所谓的。记得拓扑网络中有的点可能只做源点没有入度，那么在求最短路径中就搜索不到该点了，我们提出多源点的最短路径问题（Multisourceshortestpaths）了描述这种情况下求最短路径。其实我们可以将该问

6、题转化为单源点的最短路径问题，只需加一个哑结点，其指向所有的无入度结点，来作为新的源，而哑结点的所有边权为0。在一般图（带正环）中求最长路径问题，类似在带负环图中求最短路径问题，是NP难的。不过在无环网络中却可以求最长路径，因为无环网络无正环，所以可以确定最长的路径，而且最长路径对于DAG很有意义。所以我们先考虑在DAG中求最长路径（最短路径算法类似）：利用DAG的强大武器——拓扑排序，可以避免Dijkstra中使用优先队列的损耗，因此效率高于Dijkstra。只要按拓扑排序后的序列遍历每个结点，刷新每条边，最终就可以得到最长路

7、径了。求多源点的最长或最短路径问题可以在线性时间内解决，即复杂度E。对于所有点的最短路径，我们当然可以运行V次上一段的算法来求，这样复杂度是VE。除此以外，还存在着无环图中求所有点的最短路径，而且它可以避免多次使用拓扑排序。类似于求DAG的传递闭包问题，采用DFS和DP方法，可以得到一个有效的算法。伪代码如下：储存边的二维数组p；储存double的二维数组d；递归的函数(Graph图，int遍历结点v){遍历从v结点出发的所有边：边e=该边；intt=边的另一端；doublew=边的权；若d[s][t]>w，更新d[s][t]=

8、w,p[s][t]=e;若t未遍历，递归遍历t；遍历从t结点出发的所有边：若d[s][i]>w+d[t][i]：更新d[s][i]=w+d[t][i]，p[s][i]=e;}该算法复杂度为VE（适用于负边）。33欧几里德网络（EuclideanNetworks）