noip算法总结材料2016

《noip算法总结材料2016》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档算法总结一、动态规划和递推dp一般的解题步骤：分析问题，弄清题意——从原问题中抽象出模型——根据模型设计状态，要求状态满足最优子结构和无后效性——直接设计状态有难度的话则需要考虑转化模型——根据设计的状态考虑转移——如果过不了题目要求的数据范围，则需要考虑优化由于动态规划涉及的内容太多，只言片语难以讲清，所以附件中放了很多篇关于动态规划的文章，大部分系原创，并附上了一些经典的论文，主要讲了DP的优化，一些特殊的状态设计技巧Dp和递推没有本质区别，都是用一些状态来描述问题，并记录下一些信息，根据已知信息推出未知信息，直到得到问题的解关于DP的优化有两篇神级论文，放在附

2、件里面了，写的非常好。二、图论及网络流最小生成树：克鲁斯卡尔算法和普利姆算法，——重要性质1：最小生成树上任意两点的路径的最大边最小——重要性质2：最小生成树的多解（方案个数）只与相同权值的的边有关（省队集训题生成树计数）最短路：spfa算法、堆+迪杰斯特拉算法Spfa算法是基于松弛技术的，随机图效果极佳，最坏（网格图或存在负权环）O(nm)，适用于任意图，能够判断负权环——判负权环的方法：记录每个点当前从原点到它的最短路上边的条数，如果某次更新后这个条数>n-1则存在负权环堆+迪杰斯特拉则是用了贪心的思想，不断扩大确定dist的集合，同时更新dist，如果边权有负值就不能

3、做，复杂度是O((n+m)logn)的文案大全实用文档拓扑排序：可以将有向图转化为一个线性的序列，满足一个点所有的前驱结点都出现在这个点在序列中的位置之前。可以判断这个有向图是否有环——一个简单而实用的扩展：给树做类top排序，可以有类似的功能，即每次去掉叶子结点，将树转化为一个具有拓扑关系的序列——再扩展：树同构判断，可用类top确定树根是谁，再最小表示法+hash即可强连通分量、缩点：tarjan算法核心是每个点记一个时间戳ti[i],另外low[i]表示i点能延伸出的搜索树中节点的ti[i]的最小值，还要维护个栈记当前路径上的点，low[i]初始化为ti[i]，如果搜

4、完i了，ti[i]=low[i]则当前栈顶到i的所有点会在一个强连同分量内。关键代码：proceduredfs(i:longint);varj,k:longint;begininc(time);ti[i]:=time;v[i]:=true;low[i]:=time;inc(ed);q[ed]:=i;j:=h[i];whilej<>0dobegink:=point[j];ifti[k]=0thenbegindfs(k);iflow[k]

5、[k];j:=next[j];end;ifti[i]=low[i]thenbegininc(num);k:=0;repeatj:=q[ed];f[j]:=num;v[j]:=false;k:=k+a[j];ifb[j]thenbar[num]:=true;dec(ed);untilq[ed+1]=i;vl[num]:=k;end;end;文案大全实用文档欧拉路：含义：不重复地经过每条边的一条路径，如果起点和终点相同则叫“欧拉回路”，起点和终点不同叫“欧拉路径”存在欧拉路径的条件：至多两个点的度为基数（回路则要求全都为偶数）实现：（非常简单）一顿乱dfs就可以了，每次退栈的再

6、将这条边加入答案序列proceduredfs(i:longint);varj,k:longint;beginj:=h[i];whilej<>0dobegink:=point[j];ifw[(j+1)>>1]>0thenbegindec(w[(j+1)>>1]);dfs(k);inc(ans[0]);ans[ans[0]]:=dir[j];end;j:=next[j];end;end;上面的代码中正边和反边的编号是相邻的，关注inc(ans[0])的位置，是在递归调用的后面哈密尔顿回路含义：经过所有点的一个回路这是个NPC问题，只有近似算法（暴搜就不提了）比较好用的是模拟退火

7、，以环上相邻两点有边相连的个数作为估价值，随机化调整二分图匹配：最大匹配：匈牙利算法，理论O(nm)，实际复杂度好很多最佳匹配：KM算法，理论O(n^2m)，实际复杂度同匈牙利一样相当不错——重要性质：最小可行定标和=最优匹配文案大全实用文档KM算法中构造了一个非常不错的不等式lx[i]+ly[j]>=w[i,j]，有的题目可以利用这个不等式套KM求出最小可行定标和，如20101112ti糟糕的传染网络流非常神奇的一个东西，数学味有余而图论味不足，通常用来解决限制条件太强，以至于无论如何都表示不了状态的题，很多经典