ACM训练方案：

OJ上的一些水题（可用来练手和增加自信）

(poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094)

初期:

一.基本算法:

(1)枚举. (poj1753,poj2965)

(2)贪心(poj1328,poj2109,poj2586)

(3)递归和分治法.

(4)递推.

(5)构造法.(poj3295)

(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

(1)图的深度优先遍历和广度优先遍历.

(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)

(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)

(3)最小生成树算法(prim,kruskal)

(poj1789,poj2485,poj1258,poj3026)

(4)拓扑排序 (poj1094)

(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

pku（3692, 2239, 1719, 1469, 1466, 1422, 1274）

二分图最优匹配2195 1325

(6)最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

(1)串 (poj1035,poj3080,poj1936)

(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

(3)简单并查集的应用. (4)哈希表和二分查找等高效查找法(数的Hash,串的Hash) (poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)

(5)哈夫曼树(poj3253)

(6)堆

(7)trie树(静态建树、动态建树) (poj2513)

四.简单搜索 (1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

(1)背包问题. (poj1837,poj1276) (2)型如下表的简单DP(可参考lrj的书 page149):

1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)

2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)

3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)

六.数学

(1)组合数学:

1.加法原理和乘法原理.

2.排列组合.

3.递推关系.

(POJ3252,poj1850,poj1019,poj1942)

(2)数论.

1.素数与整除问题

2.进制位.

3.同余模运算.

(poj2635, poj3292,poj1845,poj2115)

(3)计算方法.

1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)

七.计算几何学.

(1)几何公式.

(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) (poj1408,poj1584)

(4)凸包. (poj2187,poj1113)

中级:

一.基本算法:

(1)C++的标准模版库的应用. (poj3096,poj3007)

(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

(1)差分约束系统的建立和求解. (poj1201,poj2983)

(2)最小费用最大流(poj2516,poj2516,poj2195)

(3)双连通分量(poj2942)

(4)强连通分支及其缩点.(poj2186)

(5)图的割边和割点(poj3352)

(6)最小割模型、网络流规约(poj3308, ) 三.数据结构.

(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

(2)静态二叉检索树. (poj2482,poj2352)

(3)树状树组(poj1195,poj3321，poj2155)

(4)RMQ. (poj3264,poj3368)

(5)并查集的高级应用. (poj1703,2492)

(6)KMP算法. (poj1961,poj2406) poj 2752

四.搜索

(1)最优化剪枝和可行性剪枝

(2)搜索的技巧和优化 (poj3411,poj1724)

(3)记忆化搜索(poj3373,poj1691)

五.动态规划 (1)较为复杂的动态规划(如动态规划解特别的施行商问题等)

(poj1191[棋盘分割],

poj3280（编辑距离）,

poj2029（树状数组）,

poj2948[街道问题模型],

poj1925,

poj3034

poj1054,

(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)

(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

(1)组合数学:

1.容斥原理.

2.抽屉原理.

3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).

4.递推关系和母函数.

(2)数学.

1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)

2.概率问题. (poj3071,poj3440)

3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)

(3)计算方法.

1.0/1分数规划. (poj2976)

2.三分法求解单峰(单谷)的极值.

3.矩阵法(poj3150,poj3422,poj3070)

4.迭代逼近(poj3301)

(4)随机化算法(poj3318,poj2454)

(5)杂题.

(poj1870,poj3296,poj3286,poj1095)

七.计算几何学.

(1)坐标离散化.

(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用). (poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)

(3)多边形的内核(半平面交)(poj3130,poj3335)

(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级:

一.基本算法要求:

(1)代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

(2)保证正确性和高效性. poj3434

二.图算法:

(1)度限制最小生成树和第K最短路. (poj1639)

(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解) (poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446

(3)最优比率生成树. (poj2728)

(4)最小树形图(poj3164)

(5)次小生成树.

(6)无向图、有向图的最小环

三.数据结构.

(1)trie图的建立和应用. (poj2778)

(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法

(RMQ+dfs)).(poj1330)

(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的

目的). (poj2823)

(4)左偏树(可合并堆).

(5)后缀树(非常有用的数据结构,也是赛区考题的热点).

(poj3415,poj3294)

四.搜索

(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

(1)需要用数据结构优化的动态规划.

(poj2754,poj3378,poj3017)

(2)四边形不等式理论.

(3)较难的状态DP(poj3133)

六.数学

(1)组合数学.

1.MoBius反演(poj2888,poj2154)

2.偏序关系理论.

(2)博奕论.

1.极大极小过程(poj3317,poj1085)

2.Nim问题.

七.计算几何学.

(1)半平面求交(poj3384,poj2540)

(2)可视图的建立(poj2966)

(3)点集最小圆覆盖.

(4)对踵点(poj2079)

八.综合题.

(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

-----------------------------------------------------------------------------------------

-----------------------------------------------------------------------------------------

补充

dp状态设计与方程总结

1.不完全状态记录

<1>青蛙过河问题

<2>利用区间dp

2.背包类问题

<1> 0-1背包，经典问题

<2>无限背包，经典问题

<3>判定性背包问题

<4>带附属关系的背包问题

<5> + -1背包问题

<6>双背包求最优值

<7>构造三角形问题

<8>带上下界限制的背包问题(012背包)

3.线性的动态规划问题

<1>积木游戏问题

<2>决斗（判定性问题）

<3>圆的最大多边形问题

<4>统计单词个数问题

<5>棋盘分割

<6>日程安排问题

<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)

<8>方块消除游戏(某区间可以连续消去求最大效益)

<9>资源分配问题

<10>数字三角形问题

<11>漂亮打印

<12>邮局问题与构造答案

<13>最高积木问题

<14>两段连续和最大

<15>2次幂和问题

<16>N个数的最大M段子段和

<17>交叉最大数问题

4.判定性问题的dp(如判定整除、判定可达性等)

<1>模K问题的dp

<2>特殊的模K问题，求最大(最小)模K的数

<3>变换数问题

5.单调性优化的动态规划

<1>1-SUM问题

<2>2-SUM问题

<3>序列划分问题(单调队列优化)

6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)

<1>凸多边形的三角剖分问题

<2>乘积最大问题

<3>多边形游戏(多边形边上是操作符,顶点有权值)

<4>石子合并(N^3/N^2/NLogN各种优化)

7.贪心的动态规划

<1>最优装载问题

<2>部分背包问题

<3>乘船问题

<4>贪心策略

<5>双机调度问题Johnson算法

8.状态dp

<1>牛仔射击问题(博弈类)

<2>哈密顿路径的状态dp

<3>两支点天平平衡问题

<4>一个有向图的最接近二部图

9.树型dp

<1>完美服务器问题(每个节点有3种状态)

<2>小胖守皇宫问题

<3>网络收费问题

<4>树中漫游问题

<5>树上的博弈

<6>树的最大独立集问题

<7>树的最大平衡值问题

<8>构造树的最小环

首先推荐大家一些非常简单的题，特别适合没有算法基础的新手做（需要C语言基础）。

也是我当时寒假做的题：

1000 1001 1002 1003 1004 1005 1006 1007 1008 1011 1012 1013 1017 1019 1023 1032 104

5 1046 1047 1050 1061 1067 1068 1080 1083 1088 1095 1102 1132 1159 1163 1182 1

183 1207 1218 1247 1298 1306 1308 1316 1317 1326 1331 1338 1363 1401 1423 1426

1450 1455 1477

1488 1503 1504 1517 1519 1528 1543 1547 1552 1555 1565 1575 1580 1581 1589 159

8 1606 1656 1658 1663 1674 1702 1723 1731 1753 1775 1799 1844 1851 1862 1915 1

922 1936 1953 1969 1979 2000 2001 2007 2013 2017 2027 2039 2070 2081 2105 2109

2136 2140 2141

2159 2196 2242 2246 2247 2262 2271 2301 2304 2309 2316 2328 2350 2363 2371 238

8 2390 2453 2470 2479 2487 2498 2501 2503 2507 2509 2521 2546 2551 2562 2575 2

578 2601 2602 2606 2608 2636 2656 2661 2680 2689 2707 2719 2840 2853 2871 2945

2996 3032 3062

3078 3086 3090 3094 3100 3112 3115 3117 3119 3175 3176 3181 3194 3195 3197 319

9

由于我做的题目几乎都是北大的，所以我能给大家的建议也是基于北大的。

网址：http://acm.

下面是我推荐大家做的一些题：

在1000-1999我会给大家把简单题也推荐，这些题比较经典，再一个网上有很多现成算法，

2000以后我就只推荐经典题目了。

这道题必须要做，多做几次，它会教会你如何使用一个在线的ONLINE JUDGE。

这道题最好做一下，它会教会你如何使用高精度运算，以及让你知道ACM题目中细节考虑是

多么的重要。

所谓高精度运算就是大整数的乘除法，但是这个题比较麻烦，它还需要你考虑高位的实数

，所以要记录一下小数点的位置。

简单题一道，让我初步知道什么叫做ACM中的模拟题。

模拟题就是不需要什么算法的题目，只需要按照题目要求一步一步做。

简单题一道，新手可以靠这个练习一下环境。

这道题必须要做，多写几次，不要怕超时（TIME LIMIT ERROR，以后简称TLE），或者是错

误（WRONG ANSWER，以下简称WA）。

它会告诉你什么是ACM算法中一个很重要的分支：深度优先搜索（以下简称DFS）。 做不出来不要紧，可能会花很久，也可以问人，一旦自己理解了，将会非常受益。

题目不难，但是推荐做，它是ACM中一类很重要的问题—约色夫问题的最简单形式，对于新

手很适合，我从这个题第一次学到了ACM中的数学。

非常有趣的一道题，需要加点想法进去，不是很难，推荐做。

我认为这是一个贪心的题，但是需要强大的数学证明，推荐。

数学加模拟，需要想一阵子，推荐做。

1013的升级版，挑战过1013的同学可以下来挑战这道题。

比较容易错+繁的计算几何，推荐有一定计算几何基础的同学尝试。

这道题是字符串+模拟，有字符串基础并且不怕麻烦的同学可以尝试。

经典的动态规划（以下简称DP），但是比较难，想上场的同学一定要切掉它。

又是一道经典的DP，状态压缩存储，也比较难，一定要切掉。

经典的贪心，刘汝佳的书上有详细解答。

ACM中少见的考察公式的题，会公式的话很简单。推荐物理或者数学好的新手做。

简单题，推荐新手练手。

比较麻烦的数学模拟，不推荐，但是方法还需要掌握一下。

模拟题，ACM有2类基础题，1类难，1类繁，这属于第二类。

比较基础的一道DP，但是不适合入门，当时还是费了我些时间才ACCEPT。

字符串的模拟题，比较简单，推荐新手做。

又是麻烦的模拟题，不过新手最好多练练，先把语言环境熟悉了。

关于多项式的模拟。

经典题，强烈推荐，你会学会扩展欧几里德算法，一定要切掉。

麻烦难懂的题，不过听WPT说这个是最短路，本人不推荐。

经典的贪心，强烈推荐。

恐怕是博弈论的第一道题，和黄金分割有关，打死我也想不到。

这个题我现在也不知道怎么证明，硬记公式罢了。

可以让大家了解一下，ACM中还有这么一种题。

比较有趣的一道题，不知道怎么归类，时间多的同学可以看看。

非常经典的8数码问题，一定要切掉。

不太会动态规划的同学，这道非常适合初学者。

日期处理问题，JAVA有强大的库，不过推荐大家还是练一下C的。

又是一道经典的DP，强烈推荐切掉。

高精度+一些思想。

卡特兰数，推荐的第一道组合数学题，难度适中。

很棒的模拟，做完很有成就感。

解方程的题，我是用自动机写的。这类题有一个功用的模版，强烈推荐。

很不错的模拟题，很练代码能力。

计算几何，第一道，没有什么计算几何的思想，先算入门吧。

字符串的模拟题。

计算几何，凸包+圆周长，强烈推荐。

不懂凸包是什么的可以BAIDU或者BBS询问。

非常繁杂的模拟题，不知道当时WPT是怎么切掉的。

经典的动态规划（DP），LRJ的书上也有讲，强烈推荐。

很不错的题，需要数学功底，推荐。

经典不能再经典的网络流，大家从这个题接触网络流吧，强烈推荐。

最后一位非0位是多少？这类问题有一个通用解法，从这个题可以学到。

比较简单的DP，可以给你一个全新的思想。推荐！

DP，AGAIN，比较简单，可以从这个题学习DP。

经典的搜索题，写的不好都会WA或者TLE。有难度，但是推荐。

模拟题。简单

线段树，第一道（应该说是最前面的一道），强烈推荐，LRJ书上有解答。

从这个题，大家知道并查集的新一种用法，不过通过这个题来学习并查集，并不是很容易

，有一定难度。强烈推荐。

经典的搜索+数学公式。推荐。

数学性比较强的一道动态规划。推荐

差分约束，BELLMAN-FORD算法。强烈推荐。这是一类问题。

经典的字符串自动机题目，有难度，强烈推荐！

简单题。。。不说什么，新同学练手。

非常难的计算几何，计算最大面积内核的。有意愿挑战的同学可以和我交流。

POLYA定理的最简单应用，组合数学，强烈推荐。

非常好的题目，这类题我把它叫做找规律题目，需要打表计算的。 推荐。

经典的DFS搜索题目，你可以学会回溯。

WPT把这叫做组合数学，我怎么就看不出来。。。

呵呵

不过还是推荐大家做一下。

咱交大唯一一次举办ACM比赛的题目，20xx年，大家都做做。

栈

比较强的模拟题，很容易出错。

强烈推荐，繁琐预处理+BFS，强烈推荐。

非常难的计算几何，有意愿的同学可以找我讨论。

虽然简单，但是经典，DP题，新手非常适合。

经典题，图的2分匹配，强烈推荐。

DP，有点难度，可做。

可以用贪心也可以用匹配，推荐。

类型同1312。这类题比赛经常出，要学会方法，注意边界情况的考虑。

比较简单的一个模拟题。但是写的人很少。

可以让你发疯的高精度。

FOLYD最短路算法，这个题，再合适不过。

有趣的数学问题，值得去做，推荐。

图论，欧拉回路题目，有些难度，推荐大家去做。

枚举，但是要掌握一定方法。

矩阵乘法，非常经典的DP问题了。一定要做。

棋类的模拟，怎么也得做一道吧。

组合数学经典不能再经典，简单不能再简单的题目，强烈推荐。

求三角形锤心的题目。

比较简单的计算几何，有时间可以尝试。

计算几何，但是需要一定的思考。推荐。

网络流或者2分匹配。匹配比较难想（STAR6想出来了），推荐。

过河问题，告诉你每个人速度，船一次只能带两个人过去，速度取决于慢的那一个，问所

有人过河需要最短时间。

非常经典的问题，一定要切掉，应该属于数学问题吧。

又是差分约束。

中位数问题。理解中位数求法以后就比较简单了。

表面上看是计算几何，其实是2分枚举。不过开始要排序，这样速度更快。要不然可能会T

LE。

后缀数组，这个算法本来是处理字符串的，但是在这里应用的很好。

除了后缀数组还需要加二分。具体的自己想吧，非常强烈推荐。

最小生成树题目。不难。

这个题离散书上有讲。规律很强。推荐。

无比经典一个数学题目！一定要做。你会学会质数检测与因子分解以及a ^ b mod c 的lo

g b复杂度3种算法。

都是基于__INT64的，关键很少有题像这个题数据这么完美。

这个题我是拿搜索过掉的，但是不能这样做，希望大家好好想想。

第一次让我学会了ACM有一种算法叫做构造。强烈推荐。

经典的递归式动态规划。推荐。

KMP算法的一个应用。推荐。

计算几何，包含最多点的圆。复杂度n^3，要很好优化。

想出n^2logn的请告诉我。

四道很有价值去做的题，推荐。

其中1987我还没做出来。

求a^b mod c。多做这类的题，完了以后去挑战1811。

对于新手来讲，可以先在PKU切 50道比较简单的题。

ACM题目推荐－－《算法艺术与信息学竞赛》2008-09-04 12:21一.动态规划 参考资料：

刘汝佳《算法艺术与信息学竞赛》

《算法导论》

推荐题目： http://acm./JudgeOnline/problem?id=1141

简单 http://acm./JudgeOnline/problem?id=2288

中等，经典TSP问题 http://acm./JudgeOnline/problem?id=2411

中等，状态压缩DP http://acm./JudgeOnline/problem?id=1112

中等 http://acm./JudgeOnline/problem?id=1848

中等，树形DP。

可参考《算法艺术与信息学竞赛》动态规划一节的树状模型 http://acm./show_problem.php?pid=1234

中等，《算法艺术与信息学竞赛》中的习题

http://acm./JudgeOnline/problem?id=1947 中等，《算法艺术与信息学竞赛》中的习题 http://acm./JudgeOnline/problem?id=1946 中等，《算法艺术与信息学竞赛》中的习题 http://acm./JudgeOnline/problem?id=1737 中等，递推 http://acm./JudgeOnline/problem?id=1821 中等，需要减少冗余计算 http://acm./show_problem.php?pid=2561 中等，四边形不等式的简单应用 http://acm./JudgeOnline/problem?id=1038 较难，状态压缩DP，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=1390 较难，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=3017 较难，需要配合数据结构优化（我的题目^_^） http://acm./JudgeOnline/problem?id=1682 较难，写起来比较麻烦 http://acm./JudgeOnline/problem?id=2047 较难 http://acm./JudgeOnline/problem?id=2152 难，树形DP http://acm./JudgeOnline/problem?id=3028 难，状态压缩DP，题目很有意思 http://acm./JudgeOnline/problem?id=3124 难 http://acm./JudgeOnline/problem?id=2915 非常难

二.搜索

参考资料：

刘汝佳《算法艺术与信息学竞赛》

推荐题目： http://acm./JudgeOnline/problem?id=1011

简单，深搜入门题 http://acm./JudgeOnline/problem?id=1324

中等，广搜 http://acm./JudgeOnline/problem?id=2044

中等，广搜 http://acm./JudgeOnline/problem?id=2286

较难，广搜 http://acm./JudgeOnline/problem?id=1945

难，IDA*，迭代加深搜索，需要较好的启发函数 http://acm./JudgeOnline/problem?id=2449

难，可重复K最短路，A*。

可参考解题报告: http://acm./JudgeOnline/showcontest?contest_id=1144 http://acm./JudgeOnline/problem?id=1190

难，深搜剪枝，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=1084

难，《算法艺术与信息学竞赛》习题 http://acm./JudgeOnline/problem?id=2989

难，深搜 http://acm./JudgeOnline/problem?id=1167

较难，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=1069

很难

三. 常用数据结构

参考资料：

刘汝佳《算法艺术与信息学竞赛》

《算法导论》

线段树资料： http://home./~zhuhcheng/ACM/segment_tree.pdf 树状数组资料 http://home./~zhuhcheng/ACM/tree.ppt

关于线段树和树状数组更多相关内容可在网上搜到

后缀数组资料 http://home./~zhuhcheng/ACM/suffix_array.pdf http://home./~zhuhcheng/ACM/linear_suffix.pdf 推荐题目 http://acm./JudgeOnline/problem?id=2482

较难，线段树应用，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=1151

简单，线段树应用矩形面积并，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=3225

较难，线段树应用，可参考解题报告 http://acm./JudgeOnline/showcontest?contest_id=1233 http://acm./JudgeOnline/problem?id=2155

难，二维树状数组。 http://acm./JudgeOnline/problem?id=2777

中等，线段树应用。 http://acm./JudgeOnline/problem?id=2274

难，堆的应用，《算法艺术与信息学竞赛》中有解答 http://acm./show_problem.php?pid=2334

中等，左偏树，二项式堆或其他可合并堆的应用。

左偏树参考http://www.nist.gov/dads/HTML/leftisttree.html 二项式堆参见《算法导论》相关章节 http://acm./JudgeOnline/problem?id=1182

中等，并查集 http://acm./JudgeOnline/problem?id=1816

中等，字典树 http://acm./JudgeOnline/problem?id=2778

较难，多串匹配树

参考：http://home./~zhuhcheng/ACM/zzy2004.pdf http://acm./JudgeOnline/problem?id=1743

难，后缀数组 http://acm./JudgeOnline/problem?id=2774

较难，最长公共子串，经典问题，后缀数组

http://acm./JudgeOnline/problem?id=2758

很难，后缀数组

可参考解题报告 http://acm./JudgeOnline/showcontest?contest_id=1178 http://acm./JudgeOnline/problem?id=2448

很难，数据结构综合运用

四.图论基础

参考资料：

刘汝佳《算法艺术与信息学竞赛》

《算法导论》

《网络算法与复杂性理论》谢政

推荐题目: http://acm./JudgeOnline/problem?id=2337

简单，欧拉路 http://acm./JudgeOnline/problem?id=3177

中等，无向图割边 http://acm./JudgeOnline/problem?id=2942

较难，无向图双连通分支 http://acm./JudgeOnline/problem?id=1639

中等，最小度限制生成树，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=2728

中等，最小比率生成树，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=3013

简单，最短路问题 http://acm./JudgeOnline/problem?id=1275

中等，差分约束系统，Bellman-Ford求解，《算法艺术与信息学竞赛》中有解答 http://acm./JudgeOnline/problem?id=1252

简单，Bellman-Ford http://acm./JudgeOnline/problem?id=1459

中等，网络流 http://acm./JudgeOnline/problem?id=2391

较难，网络流

http://acm./JudgeOnline/problem?id=1325

中等，二部图最大匹配 http://acm./JudgeOnline/problem?id=2226

较难，二部图最大匹配 http://acm./JudgeOnline/problem?id=2195

中等，二部图最大权匹配

KM算法参考《网络算法与复杂性理论》 http://acm./JudgeOnline/problem?id=2516

较难，二部图最大权匹配 http://acm./JudgeOnline/problem?id=1986

中等，LCA（最近公共祖先）问题

参考Tarjan's LCA algorithm 《算法导论》第21章习题 http://acm./JudgeOnline/problem?id=2723

较难，2-SAT问题

参考：http://home./~zhuhcheng/ACM/2-SAT.PPT http://acm./JudgeOnline/problem?id=2749

较难，2-SAT问题 http://acm./JudgeOnline/problem?id=3164

较难，最小树形图

参考《网络算法与复杂性理论》中朱-刘算法

解题报告范例

//考查点：会不会编程序。

//思路：此题要求输入两个数， 输出两个数的和，我用 scanf 和 printf。

// 提交情况：Wrong Answer 1次，忘了写 printf()。

Compile Error 2次，选错了语言，由于C++ 和 G++ 在 iostream.h 的不用引用方法；少一个大括号。

Accepted 1次。

// 收获：学到了 scanf, printf 的基本用法，熟悉了 OJ 的系统环境。

//经验： 写好代码后本地编译 而且需要静态 观察，杜绝编译错误。

// AC Code

#include <stdio.h>

int main() {

int a,b;

scanf("%d%d",&a,&b);

printf("%d\n",a+b);

return 0;

}