何事秋。

图论基本算法

AC自动机(4) bfs/dfs(5) bitset(3) CF刷题(23) dp一般看规律(11) dp基本算法(12) KMP(2) LCA(1) LCT(4) Prufer(2) SAM(3) STL(1) tarjan(1) 主席树/线段树(14) 二分/三分(2) 二分图(1) 位运算(1) 偏序问题(2) 分块(1) 分治/点分治/边分治(2) 单调栈(2) 单调队列(1) 博弈/sg(3) 博弈论基本算法(11) 后缀数组(1) 启发式合并(1) 哈希(4) 回文自动机(2) 图论一顿套模板(3) 基本算法(2) 多项式(1) 套题(1) 字典树(1) 字符串基本算法(27) 容斥(1) 平衡树/堆(2) 并查集(3) 序列自动机(1) 快速幂/矩阵快速幂(1) 思维只会A+B(5) 投稿(2) 拓扑序(1) 数位dp(1) 数学不好先打表(4) 数据结构基本算法(69) 数据结构瞎乱写(8) 数论分块(1) 数论只会gcd(20) 数论基本算法(64) 暴力(1) 最短路(3) 期望/概率(1) 期望dp/概率dp(1) 构造(3) 枚举(3) 树形dp(3) 树链剖分(5) 模拟只会猜题意(5) 生成树(1) 签到题(2) 线性dp(12) 线性基(2) 组合数学(1) 组合数学靠运气(2) 结论题(2) 网络流/费用流(5) 网络流基本算法(5) 群论(2) 背包dp(1) 莫比乌斯反演(1) 莫队(1) 虚树(1) 计数类dp(1) 计算几何(8) 计算几何基本算法(15) 贪心刚好过样例(3) 随机化算法(2)

/ 注册

全部文章 / 图论基本算法（共31篇）

图的遍历（DFS、DFS序，BFS）

一、DFS： const int maxn=100008; int head[maxn],nt[maxn],ver[maxn],edge[maxn]; bool ha[maxn]; void DFS(int x) { ha[x]=true; for(int i=head[x];i;...

2020-09-04

0 425

最短路——Dijkstra、Bellman-Ford、SPFA、Floyd

一、Dijkstra算法二、Bellman-Ford算法三、SPFA算法四、Floyd算法一、Dijkstra算法：无负权图的单源最短路径问题。求一张无负权图的某点到其他节点的最短距离。 1.算法思路 ①初始化dis[1]=0,其余节点的dis为正无穷大（正无穷大的一半inf/2，保...

2020-09-04

0 586

树的深度、重心、连通块划分、拓扑排序、直径

一、树的深度：树中各个节点的深度是一种自顶向下的统计信息。起初，我们已知根节点的深度为0。若节点x的深度为d（x），则它的子节点y的深度就是d（y）=d（x）+1。在深度优先遍历的过程中结合自顶向下的递推，就可以求出每个节点的深度d。 void dfs(int x) { v[x]=1...

2020-09-04

0 1028

图的类型与性质——欧拉图、（竞赛图、哈密顿图）

一、欧拉图：无向图连通性的小问题——欧拉路问题，俗称一笔画问题。给定一张无向图，若存在一条从节点S到节点T的路径，恰好不重不漏的经过每条边一次（可以重复经过图中的顶点），则称该路径为S到T的欧拉路。特别的，若存在一条从节点S出发的路径，敲好不重不漏的经过每条边一次（可以重复经过...

2020-09-04

0 853

图的搜索进阶A，IDA

一、A * ：估价函数的设计准则：估值f（state）≤未来实际代价g（state）。 A * 算法的实现，A * =优先队列BFS+估价函数。 1。优先队列BFS算法维护了一个优先队列，不断从堆中取出当前代价最小的状态进行扩展。每个状态第一次从堆中取出时，就得到了从初态到该状态的...

2020-09-04

0 465

Tarjan算法与无向图连通性

一、无向图的割点与桥的基本概念：给定无向连通图G = (V, E) 割点：对于x∈V，从图中删去节点x以及所有与x关联的边之后，G分裂为两个或两个以上不相连的子图，则称x为割点割边（桥）：若对于e∈E，从图中删去边e之后，G分裂成两个不相连的子图，则称e为G的桥或割边一般无向图...

2020-09-04

0 635

Tarjan算法与有向图连通性

一、基本概念：流图：　　给定一个有向图G= （V，E），若存在r∈V满足，满足从r出发能够到达V中所有的点，则称G是一个流图，记为（G，r），其中r是流图的源点。流图的搜索树：　　在一个流图（G,r）上从r出发，进行深度优先遍历（DFS），每个点只访问一次。所有发生递归的变（x,y）（换言...

2020-09-04

0 903

二分图的匹配

一、二分图的判定：如果一张图的N个节点可以分成A，B两个非空集合，其中A∩B＝空集，并且在同一集合内的点之间都没有边相连，那么称这张无向图为一张二分图。A，B分别称为二分图的左部和右部。定理：一张无向图是二分图，当且仅当图中不存在奇环（长度为奇数的环）。根据该定理，...

2020-09-04

0 548

二分图的覆盖与独立集

一、二分图最小点覆盖：给定一张二分图，求出一个最小的点集S，使得图中任意一条边都有至少一个端点属于S。这个问题被称为二分图的最小点覆盖，简称最小覆盖。 Konig定理：二分图最小点覆盖包含的点数等于二分图最大匹配包含的边数。证明：首先，因为最大匹配是原二分...

2020-09-04

0 562

0/1分数规划——二分、Dinkelbach

POJ2976 一、二分 #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map&...

2020-09-04

0 433