graphalgorithm.txt

acm题图算法

搜索：

poj－1198 双向BFS

poj－1324 听说是很麻烦的BFS,也不是很麻烦

poj－1077 经典8数码，广搜（2XXMS），然后构造（0MS）

poj－3240 n数码，构造

poj－1190 深搜＋剪枝 UVA跑了2S多


poj－3346 BFS，数据规模不大

poj－2046 BFS，注意状态的保存。

poj－3340 算是搜的吧

poj－3322 BFS，一次编译过掉，一次AC

poj－3328 BFS＋优先队列

poj－2034 DFS

poj－1191 DFS

poj－3288 比赛居然会想到BFS

poj-1321 DFS

poj－3221 BFS

poj-3333         MS100个点，DFS不行，可是居然就是DFS过的，汗吧。。

poj－1252 小小的BFS下

poj－2922 二分＋BFS或者DFS判断

poj－2920 BFS

poj－1465 BFS

poj-2631 DFS 2次就好了


poj - 3037 我是搜的，DP 也行


poj--3377 解题报告是o(n)的DP ，但是我BFS+优先队列过了，用dijkstra with heap也能过

poj-- 2449 第K短路,BFS A*

poj--2908 BFS+优先队列+HASH



DP：

poj－3342 树状DP

poj-2288 压缩DP

poj－2823 队列优化

poj－3303 DP，队友搜也出来过

poj－2411 压缩DP

poj－3254 压缩DP

poj－3298 算是DP吧

poj－3229 压缩DP

poj-2342 树状DP

poj－3356 LCS

poj－3141 看数据需要n^3，暂时没想出来，但是用n^4过了，也不是很慢，93MS


poj --3375 DP 优化从O(n*m) --> O(2*n^2)，只有最近点从左到右n+n这个区间


poj--3017 DP O（nlogn）堆栈+二分


图论：

poj－2516 最小费用最大流

poj－2492 最后要判断是不是一个二分图，可以用并查集减少内存

poj－1515 最后要做出一个强连通的图，对每个给的边做一次判断。

poj－2536 二分匹配

poj－2749 2－SAT判断，二分答案后判断

poj－2723 2－SAT判断，同上

poj－1161 建图，floyd一下就好了

poj－1502 floyd

poj－3156 最短路，dijkstra with heap

poj－1511 最短路，dijkstra with heap

poj－2584 我转化成最大流做的

poj－1087 最大流

poj－1149 最大流

poj－2349 dijkstra

poj－2553 强连通

poj－1275 查分约束

poj－1236 我也搞不懂算什么类型，MS有个什么证明，我胡搞出来的

poj－3249 dijkstra

poj－3255 第二短路，dijkstra一次，优先队列做一次

poj－3259 bellman_ford

poj-2485 最小生成树，0MS（至少到现在只有我一个，哈哈）

poj-1236 强连通分量

poj－3189             二分匹配

poj－2186 强连通分量

poj－3281 最大流

poj－2289 二分答案，然后对每个答案check下，每次寻找下增广路，可以就行了

poj-2762 强连通，然后判断

poj－2349 最小生成树

poj－3160 强连通＋top－sort

poj－2367 top－sort

poj－3177 桥，染色，dfs

poj－3352 和上面题一样

poj－1639 度限制生成树

poj－3013 最短路

poj－3357 最小生成树，输入输出及其恶心的题

poj－3360 题目简单，就他妈的输入处理最麻烦，还错了很多次，我都BS自己了

poj－3041 二分匹配

poj－2226 同上

poj-3164 最小树形图

tju-2248 最小树形图


UVA--11183 最小树形图,有人说要邻接边的O(VE),但是我用的O(N^3)过掉了,用了0.502S

poj-3166 建图,最短路,挺麻烦的.

poj-2402 欧拉路,中国邮政问题,找了个论文看了下,做出来居然WA,那个还是什么什么报上发表的,54他,最后搜的


ECNU-1611 最小割


poj - 2125 最小割，然后DFS求出割集


poj -- 2337 构造欧拉通路


poj-- 2060 最小路径覆盖


hit - 2543 二分+最小费用流

poj-3308 最小割 log - > pow



数据结构：

poj－3321 建树，遍历，树状数组统计，修改，统计都logn。

poj－1195 二维树状数组，每次(lognlogn)次修改

poj－3349 过不过看你hash表写的怎么样

poj－2481 二分统计技术

poj－1089 排序

poj－1984 并查集变种

poj－3264 RMQ吧

poj－3232 二分

poj－2431 堆优化下下。。就快了。。。

poj－3368 RMQ

poj－1703 并查集

poj－3274 hash


poj - 1763 排序


poj - 2187 排序


poj--3374 stern-broot tree


poj -- 1986 LCA 


poj--1470 LCA

几何：

poj－3348 凸包

poj－3355 凸包，输入输出及其恶心的题目

poj－3365 几何

其他：

poj－3279 先对第一排的2^15个状态枚举，每次n*m判断，算法O(2^m *m*n);

poj－3344 模拟

poj－3339 模拟

poj－3317 博弈极大极小 ，alpha+bata剪枝

poj－3313 这个，看懂题很重要

poj－3316 模拟搜

poj－3314 模拟

poj－2035 模拟

poj－2282 组合计数，dfs下

poj－3361 数论题目，素数

poj－3359 排列，STL就可以了

poj－2917 数学题

poj－3367 建树，遍历，好啦

poj－3370 抽屉原理

poj－3369 学会打表

poj－3366 英语题

poj－3364 组合计数

poj－3363 枚举下好啦