DP&图论 DAY 4 下午图论

DP&图论  DAY 4  下午

后天考试不考二分图,双联通

考拓扑排序

图论

图的基本模型

边:

有向边构成有向图

无向边构成无向图

权值:

1.无权

2.点权

3.边权

4.负权(dij不可以跑)

环:

1.

2.重边

3.有向无环图DAG

路径:

1.简单路径:不经过重复的点  1-->2-->3

不简单路径:经过重复点  1-->2-->3-->1-->4

2.连通,具有传递性

图:

1.树:n个点,n-1条边的无环连通图

2.完全图:一个无向图,图中任意两点之间都有一条连边

3.竞赛图:完全图中的每一条边确定一个方向

4.基环树

5.仙人掌:不是树,图里可以成环,每一条边,要么不在环上,要么只属于一个环

图的输入方式

图的存储方式

图的遍历方法

拓扑排序基于BFS

三种遍历顺序

1.前序遍历   中左右

2.中序遍历   左中右

3.后序遍历   左右中

QUS:给前序中序,写后序

前序第一个就是根,找到在中序的位置,递归

例题1:

给定一个有向图,边权为 1 或 2,求单源最短路。

>Solution

稍微改写一下 BFS 即可。
# 创建三个集合, Q0 表示当前层, Q1 表示距离为 1 的层,
Q2 表示距离为 2 的层,初始 Q0 = {s}, Q1= ∅, Q2= ∅
# 依次取出 Q0 中的点,将其邻点放入对应的 Q1 或 Q2 中
# Q0 = Q1, Q1 = Q2, Q2 = ∅
注意一个点可能和当前层既有长度为 1 的边,又有长度为 2 的
边,应当将其加入 Q1 而非 Q2。

bfs:

建立一个辅助点

每个权是2的边u→v  ,都改成   u→辅助点,辅助点→v  ,权为1 ,这样边权就都是1

bfs就行了

例题2

给出一个有向图和起点 s,对每条边 < u, v > 回答,如果删去这
条边,从 s 到 v 的最短路长度是否会改变。

>Solution

# BFS 求出从 s 出发的单源最短路
# 建立最短路图,即保留满足 dv = du + 1 的边 < u, v >

#如果询问的边不在最短路图中,那么删掉不改变
# 在最短路图上,如果 v 的入度为 1,则该入边是从 s 到 v
的必经边,若删去则 v 的最短路长度会改变
# 在最短路图上,如果 v 的入度大于 1,则删去任何一条入
边, v 的最短路长度都不会改变

拓扑排序

有向无环图的拓扑排序即将所有顶点排为线性序列,使得对于任意的 < u, v >∈ E,都有 u 在线性序列中出现于 v 之前。
有向图中如果有环,则一定不存在拓扑排序;如果没有环,则一定存在拓扑排序。

# 选取一个入度为 0 的点记为 u
# 将 u 添加到线性序列末端
# 删去所有 u 的出边
# 重复上述步骤直到所有点都被加入序列

例题1

有 n 项任务,有 m 个限制,第 i 个限制要求执行任务 ui 之前
必须要完成任务 vi。请问是否存在合适的任务执行顺序,满足所
有的限制。

>Solution

将每个任务视为一个点,任务之间的依赖构成了有向边。如果该
有向图中没有环,则存在拓扑排序,而拓扑排序就是可行的任务
执行顺序;如果该有向图中存在环,则无解。

2
有 n 项任务,有 m 个限制,限制有如下两种:
   # 执行 u 任务之前必须要完成 v 任务
   # 存在某一时刻, u 和 v 任务都在执行
请问是否存在安排每个任务起始时间和结束时间的方案,满足所
有的限制。

>Solution

为每个任务的起始时间和结束时间各对应一个点,任务 i 的起始
时间点记为 si,结束时间点记为 ei
# 要保证每个任务的结束时间在起始时间之后,所以对所有 i,连边 < si, ei >
# 如果要求任务 a 在任务 b 开始执行之前完成,则连边< ea, sb >
# 如果要求任务 a 和 b 在某个时刻都在执行,则连边< sa, eb >, < sb, ea >
对于上面的有向图,如果存在环则无解,否则根据其拓扑排序易构造一个方案。

3
对于带边权的有向无环图,求单源最短路。
>Solution

POJ 1094 Sorting It All Out
An ascending sorted sequence of distinct values is one in which
some form of a less-than operator is used to order the elements
from smallest to largest. For example, the sorted sequence A, B,
C, D implies that A < B, B < C and C < D. in this problem, we
will give you a set of relations of the form A < B and ask you to
determine whether a sorted order has been specifed or not.

由一些不同元素组成的升序序列是可以用若干个小于号将所有的
元素按从小到大的顺序 排列起来的序列。例如,排序后的序列
为 A, B, C, D,这意味着 A < B、 B < C 和 C < D。在本题中,
给定一组形如 A < B 的关系式,你的任务是判定是否存在一个
有序序列。输出到哪一项可以确定顺序或者在这一项最先出现冲
突,若所有的小于关系都处理完了都不能确定顺序也没有出现冲
突,就输出不能确定。

>Solution

# 冲突即为出现环

# 确定即为拓扑排序时队中元素不大于 1

每次取队首,队列里只有一个元素,那么顺序唯一确定

# 每次加入新的关系重新拓扑排序一次即可

BZOJ 2200 道路和航线

FJ 正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 T 个城镇 (1 ≤ T ≤ 25000),编号为 1 到 T。

这些城镇之间通过 R 条道路 (1 ≤ R ≤ 50000) 和 P 条航线(1 ≤ P ≤ 50000) 连接。

每条道路 i 或者航线 i 连接城镇 Ai 到Bi,花费为 Ci。

对于道路, 0 ≤ Ci ≤ 10000;

然而航线的花费很神奇,花费 Ci 可能是负数 (-10000 ≤ Ci ≤ 10000)。

道路是双向的,可以从 Ai 到 Bi,也可以从 Bi 到 Ai,花费都是 Ci。

然而航线与之不同,只可以从 Ai 到 Bi。

事实上,由于最近恐怖主义太嚣张,为了社会和谐,出台了一些政策保证:

如果有一条航线可以从 Ai 到 Bi,那么保证不可能通过一些道路和航线从 Bi 回到Ai。

由于 FJ 的奶牛世界公认?分给力,他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇 S 把奶牛送到每个城镇的最便宜的方案,或者知道这是不可能的。

>Solution

有向边不在环内,走拓扑排序

任何在环的地方,都是正权无向边,dij

最短路算法

Floyd 

# 基于动态规划, Fk,u,v, 表示使用点 1, 2, . . . , k 时,点 u 到点 v 的最短路

限制中间点前 k 个

# 从小到大枚举 k, u 和 v 之间的最短路要么不经过 k,要么经过 k 一次且除此之外只包含前 k - 1 个点

易见,使用二维数组不断覆盖更新即可。

时间复杂度 O(N3)
空间复杂度 O(N2)

可以处理含有负权边的情况,如果含有负环,则存在 i 使得Fi,i < 0。

出现负环,f[i][i] < 0

Floyd 传递闭包,图中任意两点的可达性

如果 i-->k , k->j ,可达,那就更新

玄学剪枝

邻接矩阵初始化

快速幂

Floyd具有矩阵乘法的一些性质,Floyd具有结合律

Dijkstra

适用于没有负权边的图。

# 将所有点分为两个集合,最短路确定的集合 S 和最短路未确定的集合 T,初始 S = {s}

# 求 T 中每个点 v 的当前最短路

# 取出 T 中 dv 最小的点,其最短路一定就是 dv,将其加入 S

# 不断重复上面的操作,直到所有点的最短路都确定

朴素写法时间复杂度较劣,可以采用堆优化至 O((N + M) logN)

Bellman-Ford

SPFA

考虑使用队列优化 Bellman-Ford 算法,如果更新了 du,则将 u 入队。每次取队首 u 更新其邻点 v 的 dv

最坏复杂度 O(NM)

原文地址:https://www.cnblogs.com/xiaoyezi-wink/p/11327282.html

时间: 08-07

DP&图论 DAY 4 下午图论的相关文章

DP&amp;图论 DAY 5 下午

DP&图论  DAY 5  下午 树链剖分  每一条边要么属于重链要么轻边 证明: https://www.cnblogs.com/sagitta/p/5660749.html 轻边重链都是交替走的(此处重链可以走若干条边) 1.dfs1 统计子树大小,确定重儿子 2.dfs2 找重链       重链,子树,分别是连续的一段 每个结点属于一个重链 ta < tb a 跳到 ta 的父节点 logn 级别 将树序列化 SPOJ QTREE Query on a tree Solution 树

DP&amp;图论 DAY 6 下午 考试

DP&图论  DAY 6  下午  考试 3 5 10 3 1 3 437 1 2 282 1 5 328 1 2 519 1 2 990 2 3 837 2 4 267 2 3 502 3 5 613 4 5 132 1 3 4 10 13 4 1 6 484 1 3 342 2 3 695 2 3 791 2 8 974 3 9 526 4 9 584 4 7 550 5 9 914 6 7 444 6 8 779 6 10 350 8 8 394 9 10 3 7 10 9 4 1 2 3

DP&amp;图论 DAY 2 下午 考试

Problem AProblem Description有一天 Tarzan 写了一篇文章,我们发现这文章当中一共出现了 n 个汉字,其中第 i 个汉字出现了 ai 次,因为 Tarzan 不希望文章被别人偷看,他要给这 n 个字分别用一个特殊的字符串表示,其中每一个字符串由两类字符组构成,一类是 a,另一类是 ha,例如 ahaha 就是由 a. ha 和 ha 构成的,我们希望帮助 Tarzan 给每个汉字一个独一无二的字符串,其中不能存在两个字符串一个是另一个的前缀.我们同时希望文章尽量短

图论概述和SPFA

图论概述和SPFA 2019-12-28 Powered by Gauss 1.图论——最短路 图论是信息学学习过程中不可或缺的一个部分.图论的应用是非常广泛的,在现实生活中大家处处都能遇到,例如电子地图,机票查询等. 现在的算法竞赛考试的范围是无边无际,但主要的考点也就是图论,DP,数论,字符串等等.图论是一大考点,例如: 题目 来源 最优贸易          NOIP2009提高组第三题 信息传递 NOIP2015提高组第二题 运输计划 NOIP2015提高组第六题 寻找道路 NOIP20

各种图论模型及其解答(转载)

原文转自Jelline blog http://blog.chinaunix.net/uid-9112803-id-411340.html //============================== 在做研究的过程中,发现其实以前觉得没什么用的数学模型或者图论模型,突然间变得非常有用起来.感叹于自己相关知识的不足,于是搜索相关知识进行学习,并分享. 这篇转载的文章对于从事网络方向研究的初级人员有一定帮助,譬如我.对于已经熟悉图论各模型.各细节的人可以直接关闭此网页离开. //=======

各种图论模型及其解答(转)

原文转自Jelline blog http://blog.chinaunix.net/uid-9112803-id-411340.html 摘要: 本文用另一种思路重新组织<图论及其应用>相关知识.首先,用通俗化语言阐述了如何对事物间联系的问题进行图论建模:接着从现实例子出发,给出 各种典型图论模型,每种图论模型对应于图论一个重要内容:再者,介绍相关知识对上述提到的图论模型涉及的问题进行解答:最后,补充一些图论其他知识,包括 图论分支.易混概念. 符号约定: Q(Question)表示对问题描

[算法模版]Tarjan爷爷的两种图论算法

[算法模版]Tarjan爷爷的两种图论算法 前言 Tarjan爷爷发明了很多图论算法,这些图论算法有很多相似之处(其中一个就是我都不会).这里会对这三种算法进行简单介绍. 定义 强连通(strongly connected): 在一个有向图\(G\)里,设两个点$ a, b \(发现,由\)a\(有一条路可以走到\)b\(,由\)b\(又有一条路可以走到\)a\(,我们就叫这两个顶点\)(a,b)$强连通. 强连通图: 如果 在一个有向图\(G\)中,每两个点都强连通,我们就叫这个图,强连通图.

DP重开

颓了差不多一周后,决定重开DP 这一周,怎么说,学了学trie树,学了学二叉堆,又学了学树状数组,差不多就这样,然后和cdc一番交流后发现,学这么多有用吗?noip的范围不就是提高篇向外扩展一下,现在向下推进度,该不会写题还是不会,水平能有什么提高,应该老老实实看完DP的所有内容和图论的基本内容,再学学数学,写写oj的题,大概暑假前就干这个吧,累的时候可以去看看莫队和CDQ 然后宣布现在DP内容记录在本章 原文地址:https://www.cnblogs.com/ywjblog/p/903318

jzoj5990. 【北大2019冬令营模拟2019.1.6】Bear (状压dp)

题面 题解 我永远讨厌dp.jpg 搞了一个下午优化复杂度最后发现只要有一个小trick就可以A了→_→.全场都插头dp就我一个状压跑得贼慢-- 不难发现我们可以状压,对于每一行,用状态\(S\)表示有哪些格子是已经被上一行推倒了的,那么我们可以枚举本行所有格子的字母情况,然后计算一下这个时候下一行格子被推倒的情况,把这一行的贡献加到下一行就行了. 简单来说就是记一个\(f[pos][S]\)表示第\(pos\)行,格子被推倒的情况为\(S\)时的方案数,\(dp[pos][S]\)为所有方案中