心情随笔amp;amp;算法笔记1

xmxm76

　　高二了，离知道NOIP已经过去一年了，感觉很彷徨，毕竟是第一次参加noip，有点担心连初赛都过不了，泉州这种神犇云集的地方ORZ；曾经想过如果自己但是不考108将而去考泉五会是什么结果，不过那样可能我就不会知道noip了吧233。感觉自己超级颓废，去年说好的刷500题的，到现在只刷了40几题，还有几题是水题233。曾经也有过许多幻想，但最终还是没能去完成，希望这次会有些结果吧，毕竟已经透支了太多的希望了，无法想象连初赛都没办法通过时自己会是怎样的心情。上学期期末考差时自己的无所谓的心情至今还会后怕，自己已经成这样了吗（笑）。
　　既然要比赛了，那就把知识点给梳理一遍吧，争取不留遗憾!_!
　　树：
　　最小生成树：
　　1、kruskal：边排序，依次取出边，只要与原来的边不构成环，就添加边，直到所有点都在树上。
　　
　　可用并查集（u所在的集合与v所在的集合）。
　　2、prim：从点出发，寻找最小边（可用堆优化），直到所有点都在树上。
　　次小生成树：听说是先算出最小生成树，然后再枚举每一边，生成环之后去掉环上权值最大的边，取所生成的树中权值最小的树。可用动态规划。
　　图：
　　单源最短径：
　　1、dijkstra（适用于权值非负的图）：分为S（原点集合）,T（最终集合），从S中取出与源点距离最小的结点u，u从S移动到T，对于所有（u,v）E，更新d[v]=min(d[v],d[u]+w(u,v)); 直到所有点都在T中。可用优先队列优化。若为稀疏图，可用邻接表。
　　2、bellman-ford（可用于含负环的图）：因为最短肯定不含环，所以最短上的结点最多只有n个，可循环n-1次，检查每条边，松驰。形式化：(白书P205）
　　2、Johnson算法：算导上看的挺云里雾里的，其实就是引进一个新结点v0，所有点与它的距离都为0，用一次bellman-ford求出其他点到v0的最短f[i]，然后对于所有（u,v）E，更新权值W(u,v)=w(u,v)+f(u)-f(v);然后对所有点进行dijkstra求出所有最短，然后再返回去d[u][v] = d[u][v] + f(v)-f(u).
　　流：
　　edmonds-karp：从0流开始，用bfs找增广，找不到增广时，即为最大流。（若为最小费用最大流问题，可用bellman-ford找增广）