NOI及NOIP需要知道的与自己的心得(3)

11 Webb.S 十二、（图论）Tarjan

其实，tarjan算法的基础是DFS。我们准备两个数组Low和Dfn。Low数组是一个标记数组，记录该点所在的强连通子图所在搜索子树的根节点的Dfn值（很绕嘴，往下看你就会明白），Dfn数组记录搜索到该点的时间，也就是第几个搜索这个点的。根据以下几条规则，经过搜索遍历该图（无需回溯）和对栈的操作，我们就可以得到该有向图的强连通分量。

数组的初始化：当首次搜索到点p时，Dfn与Low数组的值都为到该点的时间。 堆栈：每搜索到一个点，将它压入栈顶。

当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’不在栈中，p的low值为两点的low值中较小的一个。

当点p有与点p’相连时，如果此时（时间为dfn[p]时）p’在栈中，p的low值为p的low值和p’的dfn值中较小的一个。

每当搜索到一个点经过以上操作后（也就是子树已经全部遍历）的low值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。

继续搜索（或许会更换搜索的起点，因为整个有向图可能分为两个不连通的部分），直到所有点被遍历。

由于每个顶点只访问过一次，每条边也只访问过一次，我们就可以在O（n+m）的时间内求出有向图的强连通分量。 program tarjan; var

v,f:array[1..100]of boolean; dfn,low:array[1..100]of integer;

a:array[0..100,0..100]of integer; //边表 i,j,n,m,x,y,deep,d:integer; stack,ln:array[1..100]of integer; function min(x,y:longint):integer; begin

if x>y then exit(y) else exit(x); end;

procedure print(x:integer); //出栈，打印 begin

while stack[deep]<>x do begin

write(stack[deep],' '); f[stack[deep]]:=false; dec(deep); end;

writeln(stack[deep]);

f[stack[deep]]:=false; //去除入栈标记

11

12 Webb.S

dec(deep); end;

procedure dfs(x:integer); var

i:integer; begin

inc(d); //时间

dfn[x]:=d; //规则1 low[x]:=d;

inc(deep); //栈中元素个数 stack[deep]:=x; //规则2 f[x]:=true;

for i:=1 to a[x,0] do if not v[a[x,i]] then begin

v[a[x,i]]:=true; dfs(a[x,i]);

low[x]:=min(low[a[x,i]],low[x]); //规则3 end

else if f[a[x,i]] then

low[x]:=min(low[x],dfn[a[x,i]]); //规则4 if dfn[x]=low[x] then //规则5 print(x); end;

begin

readln(n,m);

fillchar(a,sizeof(a),0); for i:=1 to m do begin

readln(x,y); //读入图 inc(a[x,0]); a[x,a[x,0]]:=y; end;

for i:=1 to n do if not v[i] then begin

v[i]:=true;

dfs(i); //更换起点，规则6 end; end.

12

13 Webb.S 十三、（图论）次短路径

次短路径可以看作是k短路径问题的一种特殊情况，求k短路径有Yen算法等较为复杂的方法，对于次短路径，可以有更为简易的方法。下面介绍一种求两个顶点之间次短路径的解法。

我们要对一个有向赋权图(无向图每条边可以看作两条相反的有向边)的顶点S到T之间求次短路径，首先应求出S的单源最短路径。遍历有向图，标记出可以在最短路径上的边，加入集合K。然后枚举删除集合K中每条边，求从S到T的最短路径，记录每次求出的路径长度值，其最小值就是次短路径的长度。

在这里我们以为次短路径长度可以等于最短路径长度，如果想等，也可以看作是从S到T有不止一条最短路径。如果我们规定求从S到T大于最短路径长度的次短路径，则答案就是每次删边后大于原最短路径的S到T的最短路径长度的最小值。

用Dijkstra+堆求单源最短路径，则每次求最短路径时间复杂度为O(N*log(N+M) + M)，所以总的时间复杂度为O(N*M*log(N+M) + M^2)。该估计是较为悲观的，因为一般来说，在最短路径上的边的条数要远远小于M，所以实际效果要比预想的好。

十四、（图论）次小生成树

类比次短路径求法，很容易想到一个“枚举删除最小生成树上的每条边，再求最小生成树”的直观解法。如果用Prim+堆，每次最小生成树时间复杂度为O(N*log(N+M) + M)，枚举删除有O(N)条边，时间复杂度就是O(N^2*log(N+M) + N*M)，当图很稠密时，接近O(N^3)。这种方法简易直观，但我们有一个更简单，而且效率更高的O(N^2+M)的解法，下面介绍这种方法。

首先求出原图最小生成树，记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v)，加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边)，把它删掉，计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值，就是次小生成树。

具体实现时，更简单的方法是从每个节点i遍历整个最小生成树，定义F[j]为从i到j的路径上最大边的权值。遍历图求出F[j]的值，然后对于添加每条不在最小生成树中的边(i,j)，新的生成树权值之和就是MinST + w(i,j) – F[j]，记录其最小值，则为次小生成树。

该算法的时间复杂度为O(N^2 + M)。由于只用求一次最小生成树，可以用最简单的Prim，时间复杂度为O(N^2)。算法的瓶颈不在求最小生成树，而在O(N^2+M)的枚举加边修改，所以用更好的最小生成树算法是没有必要的。

十五、（策略）竞赛中的策略

首先通读所有的题目；草拟出算法，复杂度，数量，数据结构，微妙的细节，??

· 集体讨论所有可能的算法—— 然后选择最“笨”但却可行的算法。（注：请注意这

一点，对参赛选手来说获奖就是唯一目的）

· 进行计算！（空间和时间复杂度，并且加上实际期望和最坏情况下的数量） · 试图证明该算法错误——使用特殊的（退化的）测试数据。

· 将问题排序：根据你所需付出的努力，将能够最快解决的问题排在前面。（答题的次 序为：以前做过的，容易的，不熟悉的，难的）

13

14 Webb.S

编写程序解决一个问题—— 对每一道题而言，一次一道题

· 确定算法

· 构造特殊情况的测试数据 · 写出数据结构

· 编写并测试输入子程序（编写额外的子程序来显示数据输入的正确性） · 编写并测试输出子程序

· 逐步细化：通过写注释来刻划程序的逻辑轮廓 · 一个部分一个部分地填充并调试代码

· 完成代码使其正常运转，并验证代码的正确性（使用一般情况的测试数据） · 试图证明代码错误——使用特殊情况的测试数据来验证代码正确性

· 逐渐优化——但足够了即可，并且保存所有的版本（使用最坏情况的（即运行时间

长的）测试数据来计算出实际运行时间）

时间安排策略和“故障控制”方案

制定一个计划决定在各种（可预测的）故障发生时的行动；想象你可能遇到的问题并计算出 你所希望做出的反应。核心问题是：“你何时花费更多的时间在调试程序上，你何时放弃并 继续做下一题？”。考虑以下问题： · 你已经花费了多长时间来调试它？ · 你可能有什么样的BUG？ · 你的算法有错吗？

· 你的数据结构需要改变吗？

· 你是否对什么地方可能会出错有一些头绪？

· 花费较短的时间（20 分钟）在调试上比切换去做其他别的事要好；但是你或许能够 在45 分钟内解决另一个问题（ A short amount (20 mins) of debugging is better than switching to anything else; but you might be ableto solve another from scratch in 45 mins.） · 你何时返回到一个你先前放弃的问题？

· 你何时花费较多的时间优化一个程序，你何时放弃当前优化工作而切换去作其他 事？

· 从这点考虑出去（Consider from here out）——忘记先前的努力，着眼于将来： 你如何才能就你目前所有的抓住下一个小时。

在你上交你的答案之前列出一个校验表：

· 在竞赛结束前五分钟结束编写代码（Code freeze five minutes before end of

contest）。

· 将所有的声明关闭。 · 将调试输出关闭。

· 确认输入输出文件名正确。 · 确认输入输出格式正确。 · 重新编译并再测试一次。

· 将文件以正确的文件名复制到正确的位置（软盘）。

提示和技巧

· 如果可以就用暴力法（即穷举法）解决（注：居然将这条作为技巧，可见竞赛的目

的就是获奖，为此要“不择手段”。）

· KISS(=Keep It Simple, Stupid)：简单就好！（KISS: Simple is smart!） · 提示：注意限制（在问题陈述中指明）

14

15 Webb.S

· 如果可以给你带来方便的话就浪费内存（假如你能侥幸逃脱规则处罚的话） · 不要删除你额外的调试输出，将它注释起来 · 逐渐地优化，足够了即可 · 保留所有的工作版本 · 编码到调试：

o 注意留有空白（whitespace is good） o 使用有意义的变量名 o 不要重复使用变量 o 逐步细化

o 在写代码之前先写注释 · 有可能的话尽量避免使用指针

· 避免使用麻烦的动态内存：静态地分配所有的东西。

· 尽量不要使用浮点数；如果你不得不使用，在所有使用的地方设置允许的误差（绝

对不要测试两个浮点数相等） · 如何写注释：

o 不要写得太长，简洁的注解就可以了

o 解释复杂的功能：++i; /* increase the value of i by 1*/ 这样的注释 是毫无意义的。 o 解释代码中的技巧

o 将功能模块划定界限并且归档（ Delimit & document functional sections）

o 注释要好像是写给某个了解该问题但并不了解程序代码的聪明人看的 o 对任何你不得不考虑的东西加以注释

o 在任何你看到了以后会问“他到底干什么用”的地方加注释（Anything you looked at even once saying, \） o 总是注释数组的索引次序

· 记录你每一次竞赛的情况：成功之处、犯的错误，以及何处你可以做得更好；利用 这些记录来改进你的策略。

复杂度

基础和阶符号

复杂度分析的基本原理围绕着符号大“O”，例如：O(N).这意味着算法的执行速度或内存占 用将会随着问题规模的增倍而增倍。一个有着O(N 2)的算法在问题的规模增倍时其运行时间 将会减慢4 倍（或者消耗4 倍的空间）。常数时间或空间消耗的算法用O(1)表示。这个概念 同时适用于时间和空间；这里我们将集中讨论时间。 一种推算一个程序的O( ) 运行时间的方法是检查它的循环。嵌套最深的（因而也是最慢的） 循环支配着运行时间，同时它也是在讨论O( ) 符号时唯一考虑的循环。有一个单重循环和 一个单层嵌套循环（假设每个循环每次执行N 次）的程序的复杂度的阶是O(N 2)，尽管程序 中同时有一个O(N)循环。

当然，递归也像循环一样计算，并且递归程序可以有像O(b N)， O(N!)， 甚至O(N N)的阶。

经验法则

· 在分析一个算法以计算出对于一个给定的数据集它可能要运行多长时间的时候，第

一条经验法则是：现代（1999）计算机每秒可以进行10M 次操作。对于一个有五秒 钟时间限制的程序，大约可以处理50M 次操作。真正优化的好的程序或许可以处理 2 倍甚至4 倍于这个数目的操作。复杂的算法或许只能处理这个数目的一半。

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库NOI及NOIP需要知道的与自己的心得(3)在线全文阅读。