OI刷题录——图论.pdfVIP

OI 刷题录——图论 前言 省选过后写了一些图论题，从中选出50 道集合 在这里，给想写图论的一点帮助。大部分较为基础， 神犇就不要过来虐我了。 大部分题目是POJ 的，每道题后都给出我提交情 况，写明WA ，TLE ，RE 等的原因，方便大家吸取教 训。 50 道题目包括：最短路3 道，Tarjan 4 道，最小 生成树3 道，差分约束系统6 道，网络流29 道（包 含线性规划与网络流24 题），杂项5 道。 提供我的每道题AC 代码以及其他资料的压缩包，以 下为下载地址：百度云网盘 115 网盘 最短路 spfa ，dijkstra 为图论基础算法，应熟练应用。 spfa 是可以扩展到二维的。 先将距离小于等于R 的点对连无向边，形成一张图。 dist[i][j] 表示从j 到达i 时的最短路，朝向为 向量(xi-xj ，yi-yj) 。 spfa 时枚举跟 i 相连的点 k ，由状态 dist[i][j]转移到状态 dist[k][i] ，更新完dist[k][i] 的值后将其入队(如果还未入队的 话) 。 spfa 结束后取Min{dist[n][i]} ， 1 ≤i ＜n。 本题关键在于计算向量转角，题目中已经提示使用atan2( ) 。 atan2(x ，y) ：返回向量(x，y) 跟x 轴正方向的夹角(弧度制) ， 值域为(- π，π] ，(x，y)在x 轴上方返回值为正，下方为负。 两向量夹角：D=abs(atan2(x1 ，y1)-atan2(x2 ，y2)) ，如果 D π，则D=2 π-D ，最后应转成角度制即 D=D/ π*180 。 Compile Error ：POJ 下sqrt 和atan2 应进行强制类型转换。 Wrong Answer ：最开始没有用atan2 ，用了比较矬的方法。 滑槽顶、楼梯底和终点为传送入口，滑槽底、楼梯顶和起点 为传送出口。一旦达到入口就会被送到出口。 从每个出口向其后面的每个入口连一条有向边，贪心计算步 数作为权值，然后跑一遍spfa 即可得出答案。 步数计算： 1、一开始将步长定为最大，以这步长前进。 2 、如果会踩到中途某一传送入口则减小步长，如果还是入 口则再减小，减小到不是入口用最大步跨过去，继续以最大 步前进，又遇到入口则重复操作。 3 、如果一直减少到步长为 1 还是入口，则正在枚举的这两 点之间不连边。 Wrong Answer ： 1、循环队列应head!=tail ，写成headtail。 2 、没有想到减小步长后还有可能是入口，应继续减小。 floyd 矩阵快速幂。 将 floyd 与矩阵乘法结合起来，写成这种形式： C[i][j]=Min{A[i][k]+B[k][j]} ， 1 ≤i,j,k ≤n。 这样如果A 矩阵表示经过k1 条边的最短路，B 矩阵表示经过 k2 条边的最短路，那C 矩阵表示经过(k1+k2)条边的最短路。 于是便可以用矩阵快速幂。 由于不是在原矩阵上操作，所以本题的floyd 过程(或者说矩 阵乘法过程) 三重循环时可以将k 那层放在最里层。 Time Limit Exceeded ：由于将快速幂改写非递归式的，还未 写熟练，所以写挫了。 Wrong Answer ：同上。 Tarjan 包括强连通分量，双连通分量(割边，割点) 。 一个强连通分量里的顶点互相可达，本题只要求单向可达， 考虑先求强连通分量缩点。 缩点之后就会变成有向无环图。 显然，有向无环图中每对顶点单向可达，则必定是一条链， 若有分支，则位于不同分支上的点之间不存在路径。 所以本题只需求完强连通分量后判断新图是否是一条链。 链的判定： 方法一、dp 求图的最长链看链上的点数是否等于连通块数。 方法二、对有向无环图进行拓扑排序，某一时刻度为0 的点 多于1 个则证明存在分支。 Wrong Answer ：tarjan 时连通分量退栈最后一个忘了top-- 。 任意两点间均有两条边不相交的路径是边双连通分量，显然 先tarjan 求割边和双连通分量。 双连通分量和割边构成一棵树，统计叶子节点(度为 1 的点