Daowuu

图论

动态规划(1) 博弈论(1) 字符串(5) 数学(10) 数据结构(3) 未归档(1) 计算几何(8) 题解(2) 高精度(1)

/ 注册

全部文章 / 图论（共9篇）

最小割来自专栏

s-t 最小割最小割问题可以形象地理解为：为了不让水从 s 流向 t，怎么破坏水沟代价最小？被破坏的水沟必然是从 s 到 t 的单向水沟。而在有向图流网络 G = (V，E) 中，割把图分成 S 和 T = V - S 两部分，源点 s ∈ S，汇点 t ∈ T，这称为 s - t 割。最大流最小...

图论

2020-09-02

0 697

费用流来自专栏

最小费用最大流假设每条边除了有一个容量限制外，还有一个单位流量所需的费用(cost)。该网络中花费最小的最大流称为最小费用最大流，即总流量最大的情况下，总费用最小的流。证：在残余网络上求最短路是最小费用设有 f 为以以上方式求出的结果，设 f ’ 和 f 流量相同，但是费用更少因为...

图论

2020-08-25

1 1504

最大流来自专栏

概述我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。最大流算法有很多种，基本上分为两类：1.“增广路”算法。例如 Edmonds-Karp 算法、Dinic 算法、ISAP 算法。2.“预流推进”算法。例如 Ford-Fulkerson 增广路方法残...

图论

2020-08-21

0 649

二分图来自专栏

二分图匹配二分图：把无向图 G = （V，E）分为两个集合 V1，V2，所有的边都在 V1 和 V2 之间，而 V1 或 V2 的内部没有边。V1 中的一个点与 V2 中的一个点关联，称为匹配。染色法：一个图是否为二分图，一般用“染色法”进行判断。用两种颜色对所有顶点进行染色，要求一条边所连接的两...

图论

2020-08-16

0 630

LCA 来自专栏

最近公共祖先 LCA（Least Common Ancestors），即最近公共祖先，指对于有根树 T 的两个结点 u 、v ，最近公共祖先 LCA(T,u,v) 表示一个结点 x, 满足 x 是 u、v 的祖先且 x 的深度尽可能大。树上倍增 int anc[maxn][32]; // 结点...

lca

2020-07-29

0 647

无向图的连通性来自专栏

割点和割边在无向图中，所有能互通的点组成了一个“连通分量”。在一个连通分量中有一些关键的点，如果删除它，会把这个连通分量分成两个或更多，这种点称为割点（cut vertex）。在一个连通分量中，如果删除一条边，把这个连通分量分成两个，这个边称为割边（cut eddge，又称为桥，bridge）。 ...

图论

2020-07-26

0 1040

最小生成树（MST）来自专栏

最小生成树最小生成是无向图中的一个问题。 kruskal 算法时间复杂度，m 为边的个数对边进行排序。用并查集处理连通性问题。 const int maxn = 1e6+1; struct E{ // 图中的边 int u, v, w; }e[maxn]; //stru...

最小生成树图论

2020-07-23

0 554

最短路来自专栏

最短路径问题在一个图中有 n 个点、m 条边。边有权值，例如费用、长度等，权值可正可负。边可能是有向的，也可能是无向的。给定两个点，起点是 s，终点是 t，在所有能连接 s 和 t 的路径中寻找边的权值之和最小的路径，这就是最短路径问题。注：若图中存在负圈，则不存在最短路问题，若存在负边权，则不能...

2020-07-20

1 705

有向图的连通性来自专栏

强连通分量（SCC）如果一个有向图G不是强连通图，那么可以把它分成多个子图，其中每个子图的内部是强连通的，而且这些子图已经扩展到最大，不能与子图外的任意点强连通，称这样的一个“极大强连通”子图是G的一个强连通分量。 Kosaraju算法时间复杂度 O(N+E) Kosaraju 算法用到了“...

图论

2020-07-11

0 1012