首页 > 其他分享 >图论总结

图论总结

时间：2023-10-06 18:11:46浏览次数：43  
标签：总结 图论 匹配 int ++ dfn low 节点

最小生成树相关

次小生成树、生成树边替代

对于一条非树边 \((u,v)\)，它替代树 \(u,v\) 链上的最大值，对答案的影响最小。用倍增或树链剖分维护。

对于一条树边，如果非树边 \((u,v)\) 满足这条边在链 \(u,v\) 上，它被满足这个条件的权值最小的边替代对答案的影响最小。把非树边按权值排序，用并查集进行路径压缩。

\(k\) 路归并（二路归并）

有 \(k\)(\(2\)) 个序列，每个序列选一个数，求所有选数方案前 \(k\) 小和。

多次进行二路归并来实现 \(k\) 路归并。

二路归并可以用堆实现，时间复杂度 \(O(k\log k)\)；也可以直接归并，这样整个 \(k\) 路归并的时间复杂度为 \(O(nk)\)。

于是，你就可以求仙人掌 \(k\) 小生成树。（这玩意真的有用吗）

Kruskal 与状压 DP

DP 记录当前并查集的状态，状态数量是集合划分的方案数，也就是 Bell 数，可以哈希存状态，手写哈希并用栈记录状态常数小，但代码难写。其实还好。

Kruskal 重构树

1. 定义与构造

对于一张无向图，新建 \(n\) 个树，原图每个点在一个树中，权值是 \(0\)。按边权从小到大枚举边，如果这条边两个节点不在一棵树，合并两个节点所在的树。新建一个点，点权为加入边的边权，同时将两棵树的根节点分别设为新建点的左儿子和右儿子，将新建点设为根。

实现与 Kruskal 最小生成树算法类似，用并查集实现。

代码：

struct edge{
int u, v, w;
bool operator <(const edge &p) const
{
return w < p.w;
}
}e[N];

int gfa(int i)
{
return i == fa[i] ? i : (fa[i] = gfa(fa[i]));
}

void Kruskal()
{
for(int i = 1; i < n * 2; i ++ ) fa[i] = i;
k = n;
sort(e + 1, e + m + 1);
for(int i = 1; i <= m; i ++ )
{
int u = gfa(e[i].u), v = gfa(e[i].v);
if(u != v)
{
w[ ++ k] = e[i].w;
ls[k] = u, rs[k] = v;
f[u] = f[v] = fa[u] = fa[v] = k;
}
}
}

2. 性质与应用

kruskal 重构树有以下性质：

  • 如果原图连通，重构树是一棵 \(2n-1\) 个节点的二叉树，根节点是最后插入的节点，每个编号小于等于 \(n\) 的节点没有儿子，编号大于 \(n\) 的节点有两个儿子。
  • 满足大根堆的性质，即每个节点权值大于等于儿子节点权值。
  • 原图中两个点之间的所有路径上最大边权的最小值等于 Kruskal 重构树上两点之间的 LCA 的权值。

由这些性质，kruskal 重构树主要有两种应用（可能不全，碰到再补充）：

  • 在线求一个无向图两点间简单路径的最大边权最小值。
  • 在线修改和查询所有可以由一个点 \(u\) 不通过权值大于 \(w\) 的点的信息：用树上倍增找到 \(u\) 父节点中满足权值小于等于 \(w\) 的深度最浅的节点 \(v\)，则满足条件的点是 \(v\) 的子树中所有叶子节点。

实际上对于第二个应用，如果不强制在线且没有修改操作，可以用并查集实现：边按权排序，询问按 \(w\) 排序，处理每个询问前用并查集连边权小于 \(w\) 的边，用并查集处理询问，时间复杂度 \(O(nlogn)\)

3. 题目

(1) P3684 [CERC2016]机棚障碍 Hangar Hurdles

链接

首先用二分法求出每个点为中心的正方形最大边长，然后所有相邻的点连一条边权值为两个点最大边长的最小值，问题转化为在无向图上求两个点路径最小边权最大值，构建 kruskal 重构树求 LCA 即可。时间复杂度 \(O(n^2logn)\)

代码

// 求最大正方形边长

int get(int ax, int ay, int bx, int by)
{
return s[bx][by] - s[ax - 1][by] - s[bx][ay - 1] + s[ax - 1][ay - 1];
}

for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] == '#');

for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
{
int l = 0, r = min(min(i, n - i + 1), min(j, n - j + 1)), mid;
while(l < r)
{
mid = l + r + 1 >> 1;
if(get(i - mid + 1, j - mid + 1, i + mid - 1, j + mid - 1)) r = mid - 1;
else l = mid;
}
t[i][j] = l;
}

// Kruskal 重构树

void kruscal()
{
k = n * n;
for(int i = 1; i < k * 2; i ++ ) fa[i] = i;
sort(e + 1, e + m + 1);
for(int i = 1; i <= m; i ++ )
{
int u = gfa(e[i].u), v = gfa(e[i].v);
if(u != v)
{
w[ ++ k] = e[i].w;
ls[k] = u, rs[k] = v;
f[u][0] = f[v][0] = fa[u] = fa[v] = k;
}
}
}

void dfs(int u)
{
dep[u] = dep[f[u][0]] + 1;
for(int i = 1; i < K; i ++ ) f[u][i] = f[f[u][i - 1]][i - 1];
if(ls[u]) dfs(ls[u]), dfs(rs[u]);
}

int lca(int u, int v)
{
if(dep[u] < dep[v]) swap(u, v);
for(int i = K - 1; i >= 0; i -- )
if(dep[f[u][i]] >= dep[v])
u = f[u][i];
if(u == v) return u;
for(int i = K - 1; i >= 0; i -- )
if(f[u][i] != f[v][i])
u = f[u][i], v = f[v][i];
return f[u][0];
}

// 调用

w[lca(u, v)];

(2) 万松园

题意描述：给定一棵 \(n\) 个节点的树，多次询问，每次询问给定 \(u,w\)，求 \(u\) 不经过边权小于 \(w\) 的边能到达点的数量。

第二个运用。记录重构树上每个 \(2^k\) 级祖先，查询时从大到小枚举 \(k\)，如果 \(u\) 的 \(2^k\) 级祖先的权值大于等于 \(w\)，\(u\) 设为 \(u\) 的 \(2^k\) 级祖先。

因为不强制在线，用并查集可以做而且思路比较简单。

可以发现，无论是并查集的离线做法还是 Kruskal 重构树的在线做法，重构树的在线做法，原图是树的条件没有多大作用，只是合并的时候可以不用判断是否在一个集合，也就是说，一般的无向图也可以用这种做法。所以，这个条件是用来钓鱼的

代码

int gfa(int i)
{
return i == fa[i] ? i : (fa[i] = gfa(fa[i]));
}

void kruskal()
{
sort(e + 1, e + m + 1);
for(int i = 1; i < n * 2; i ++ ) fa[i] = i;
k = n;
for(int i = 1; i <= m; i ++ )
{
int u = gfa(e[i].u), v = gfa(e[i].v);
w[ ++ k] = e[i].w;
ls[k] = u, rs[k] = v;
f[u][0] = f[v][0] = fa[u] = fa[v] = k;
}
w[0] = -1;
}

void dfs(int u)
{
for(int i = 1; i < K; i ++ ) f[u][i] = f[f[u][i - 1]][i - 1];
if(ls[u])
{
dfs(ls[u]), dfs(rs[u]);
cnt[u] = cnt[ls[u]] + cnt[rs[u]];
}
else cnt[u] = 1;
}

int query(int u, int k)
{
for(int i = K - 1; i >= 0; i -- )
if(w[f[u][i]] >= k)
u = f[u][i];
return cnt[u] - 1;
}

(3) P4768 [NOI2018] 归程

链接

首先可以想到求所有点到终点的最短路径，即节点 1 到所有点的最短路径，用Dijkstra 算法求（SPFA 就在这里死的）。

问题转换为给定 \(u,w\)，求 \(u\) 不经过边权小于等于 \(w\) 的边能到达点的到 1 节点的距离的最小值，构造 kruskal 重构树用书上倍增解。

代码

void dijkstra()
{
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
memset(mark, 0, sizeof mark);
priority_queue<PII, vector<PII>, greater<PII> > pq;
pq.push({0, 1});

while(pq.size())
{
int u = pq.top().y;
pq.pop();
if(mark[u]) continue;
mark[u] = true;

for(int i = h[u]; i; i = ne[i])
{
int v = en[i];
if(dis[v] > dis[u] + le[i])
{
dis[v] = dis[u] + le[i];
pq.push({dis[v], v});
}
}
}
}

int gfa(int i)
{
return i == fa[i] ? i : (fa[i] = gfa(fa[i]));
}

void kruskal()
{
for(int i = 1; i < n * 2; i ++ ) fa[i] = i;
k = n;
sort(e + 1, e + m + 1);
for(int i = 1; i <= m; i ++ )
{
int u = gfa(e[i].u), v = gfa(e[i].v);
if(u != v)
{
w[ ++ k] = e[i].w;
ls[k] = u, rs[k] = v;
f[u][0] = f[v][0] = fa[u] = fa[v] = k;
}
}
w[0] = -INF;
}

void dfs(int u)
{
for(int i = 1; i < K; i ++ ) f[u][i] = f[f[u][i - 1]][i - 1];
mindis[u] = dis[u];
if(ls[u]) dfs(ls[u]), mindis[u] = min(mindis[u], mindis[ls[u]]);
if(rs[u]) dfs(rs[u]), mindis[u] = min(mindis[u], mindis[rs[u]]);
}

int query(int u, int t)
{
for(int i = K - 1; i >= 0; i -- )
if(w[f[u][i]] > t)
u = f[u][i];
return mindis[u];
}

(4) Donation

链接

在 kruskal 重构树上 dp，题解。

总结

最大边最小=最小 \(x\) 保留大于等于 \(x\) 的边连通=最小生成树。

两两之间最小瓶颈最大值=重构树按 DFS 序排序后相邻两点 LCA 权值最大值。

计算一条边的贡献。

找权值满足要求深度最小的点，除了倍增以外，还可以树剖+二分。

最短路相关

补图处理

用一个链表记录还没有遍历的节点，把每个节点不能到达的节点排序，用双指针求当前节点能到达哪些未被遍历的节点并遍历。

最短路的虚点优化建图、拆点、最短路上的边

二进制分组

用于计算两两之间的最大贡献、不能自己贡献自己。把元素按二进制第 \(i\) 位分为两组互相计算贡献，则仅需计算 \(\log n\) 次。

bellmanford 与可达性判断

可以用来求解无法直接建图的复杂情况。

欧拉路径、欧拉路径拆分

用邻接表遍历，每遍历一条边就删掉它。

拆分见守卫王国。

dijstra 与成环转移 DP

用 dijstra 的方式来更新状态，需要满足一个状态不能被它更新其它状态之前值比它小的状态更新，即不能有负权边。

最短路径树

连通性相关

强连通

模板

void tarjan(int u)
{
dfn[u] = low[u] = ++ dfst;
sta[ ++ tt] = u;
insta[u] = true;
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(insta[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
scc ++ ;
int v;
do{
v = sta[tt -- ];
insta[v] = false;
bel[v] = scc;
}while(v != u);
}
}

缩点

把一个强连通分量缩成一个点，因为这个强连通分量内的点可以经过任意这个强连通分量的点到达任意强连通分量的点，这样就可以形成一个有向无环图，方便处理。

  1. 直接利用性质：入度、出度为 \(0\) 的点。
  2. DP：最长路（原图中可以多次经过同一个、点经过的点只计算一次贡献的最长路）、可达性（可以通过 bitset 优化后时间复杂度为 \(O\left(\frac{nm}{32}\right)\)，略低于 floyd 算法）。由于 tarjan 的过程已经进行了拓扑排序，且强连通分量的编号靠后的拓扑序靠前，所以不需要再拓扑排序。注意：如果要计算方案，要使缩点后的图没有重边（根据具体情况确定）。

边双连通

模板

桥：

idx = 1;
void tarjan(int u, int fr)
{
dfn[u] = low[u] = ++ dfst;
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(!dfn[v])
{
tarjan(v, i);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u]) bridge[i] = bridge[i ^ 1] = 1;
}
else if(i != (fr ^ 1)) low[u] = min(low[u], dfn[v]);
}
}

边双连通分量：

void tarjan(int u, int fr)
{
dfn[u] = low[u] = ++ dfst;
sta[ ++ tt] = u;
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(!dfn[v])
{
tarjan(v, i);
low[u] = min(low[u], low[v]);
}
else if(i != (fr ^ 1)) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u])
{
int v;
scc ++ ;
do{
v = sta[tt -- ];
bel[v] = scc;
w1[scc] += st1[v], w2[scc] += st2[v];
}while(v != u);
}
}

缩点

缩点之后形成一棵树。主要用于求解段了一条边连通性，也可以用于求“对每条边确定一个方向”的路径问题。

点双连通

模板

割点：

void tarjan(int u)
{
dfn[u] = low[u] = ++ dfst;
sta[ ++ tt] = u;
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) cut[u] ++ ;
}
else low[u] = min(low[u], dfn[v]);
}
if(u != rt) cut[u] ++ ;
}
// cut[u] > 1 则 u 是割点

点双连通分量：

void tarjan(int u)
{
dfn[u] = low[u] = ++ dfst;
sta[ ++ tt] = u;
for(int i = la[u]; i; i = ne[i])
{
int v = en[i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u])
{
scc ++ ;
int x;
do{
x = sta[tt -- ];
dcc[scc].push_back(x);
cut[x] ++ ;
}while(x != v);
dcc[scc].push_back(u);
cut[u] ++ ;
}
}
else low[u] = min(low[u], dfn[v]);
}
}

块-割点树

对于每个点双连通分量建一个节点与这个点双连通分量里的割点连边。用来处理与割点相关的问题。

圆方树

对于每个点双连通分量建一个节点与这个点双连通分量里的点连边。可以利用点双连通图的性质解决问题。

二分图相关

定理

  • 增广路定理：一个图为最大匹配等价于不存在增广路。
  • Hall 定理：
  • 一个二分图存在完全匹配当且仅当点数较小的一侧的点，它的任意一个点集相连的点的数量大于等于点集的大小。
  • 一个二分图的最大匹配为点数较小的一侧的点的点数，减去它的一个点集相连的点的数量与点集的大小的差的最小值。
  • Kőnig 定理：二分图最小点覆盖等于最大匹配。构造方案：进行最大匹配之后，从左侧每个非匹配点出发，非匹配边、匹配边交替行走（即匈牙利算法实现的过程），标记能够到达的点，则左边未标记的点和右边标记的点组成一个点覆盖且数量等于最大匹配数。
  • 独立集的补集为覆盖集。
  • 团在补图中为独立集。
  • Dilworth 定理：偏序集能划分成的最少的全序集个数等于最大反链的元素个数。在一个 DAG 中，最大的点集使两两之间没有边，等于最小路径划分。

算法

  • 染色法判断二分图。

  • 匈牙利算法

  • 把所有点按一定顺序进行增广，时间复杂度 \(O(nm)\)。
  • 在对一个点进行増广之前，这个点是非匹配点。
  • 通过调整増广的顺序，可以解决一些字典序问题，如变换序列。注意：对于一般图不能直接倒序增广，考虑这个方法：先求出一个最大匹配，然后从前往后枚举每个点，枚举与它连边的点，将它原来的匹配删除，固定这两个点的匹配，判断是否可以重新增广，时间复杂度 \(O(m^2)\)。似乎可以直接断掉原来的匹配后从小到大增广，时间复杂度 \(O(nm)\)。
  • 如果图要改变，可以只对影响的点进行增广。
  • HK 算法
  • 与 Dinic 算法类似，运用多路增广算法。
  • 首先 BFS 进行分层，非匹配边方向从左往右，匹配边方向从右向左，求非匹配点到匹配点的最短路径，同时判断是否存在增广路。
  • DFS 进行增广，增广路必须满足下一个点是这个点层数加 \(1\)。
  • 可以证明时间复杂度 \(O(m\sqrt {n})\)。

模型

  • 二分图判断。
  • 最大匹配。
  • 最小点覆盖。
  • 最大独立集。
  • DAG 的最小路径划分：拆点，对于原图中的边 \((u,v)\)，新图中是 \((u,v')\)，最小路径划分为 \(n-\text{最大匹配}\)。方案为：从每个右侧的非匹配点出发，对应的左侧的点，这个点的匹配，对应的左侧的点……这样构成一条路径。
  • DAG 的最小路径（可重复）覆盖：求传递闭包，转化为上问题。
  • DAG 的最大不可达点集：求传递闭包，转化求最大反链。
  • 有向图环划分：建图方式同 DAG 的最小路径划分，存在环划分等价于二分图存在完美匹配。
  • 二分图博弈：给定一张二分图和棋子初始位置，先后手交替移动棋子，并把移动前棋子所在节点删除，不能操作者失败。先手必胜等价于棋子的初始位置是在所有的最大匹配中，也就是删去这个节点后，最大匹配会变小。证明：
  • 如果当前棋子位置没有边，则先手必败，此时这个节点不在任何最大匹配中。
  • 如果当前棋子位置 \(u\) 在所有最大匹配中，则先手移动到任意一个它的匹配 \(v\)，假设后手移动到 \(w\)，且 \(w\) 在新图中不在所有最大匹配中，则可以用 \((w,v)\) 的匹配替换 \((u,v)\) 的匹配，矛盾，所以 \(w\) 一定在所有最大匹配中。
  • 如果当前棋子位置 \(u\) 不在所有最大匹配中，建一个新点 \(v\) 只与 \(u\) 连边，由于 \(u\) 不在所有最大匹配中，则一定可以存在匹配 \((u,v)\)，所以 \(u\) 不能到达不在所有最大匹配中的点。

标签：总结,图论,匹配,int,++,dfn,low,节点
From： https://www.cnblogs.com/recollect-the-past/p/17744794.html

相关文章

  • 2023-2024-1 学号20231315《计算机基础与程序设计》第二周学习总结
    学期：2023-2024-1学号：20231315《计算机基础与程序设计》第二周学习总结作业信息这个作业属于哪个课程2023-2024-1《计算机基础与程序设计》这个作业要求在哪里2023-2024-1《计算机基础与程序设计》这个作业的目标学习计算机科学概论第1章和《C语言程序设计》第1......
  • 10月2总结
    在学习中使用哪些工具“工欲善其事必先利其器。”在网络技术的学习过程中，往往需要使用一些工具，来辅助我们学习，以此将抽象的技术通过具体的方式来表现出来，便于加深网络理论的印象。今天，我将列举我在学习过程中使用过的工具。以网络仿真工具为例，建议初学者选择一个厂商的软件作为......
  • 10月6日总结
    访问者模式（VisitorPattern）是一种强大的行为型设计模式，它允许你在不改变被访问对象的类的前提下，定义新的操作和行为。本文将详细介绍访问者模式，包括其定义、举例说明、结构、实现步骤、Java代码实现、典型应用场景、优缺点、类似模式以及最后的小结。1模式的定义访问者模式允许......
  • 10月5日总结
    四、用go语言，重写ENQUEUE和DEQUEUE的代码，使之能处理队列的下溢和上溢。文心一言：在Go语言中，我们可以使用切片来实现队列。下面是如何实现ENQUEUE和DEQUEUE操作，同时处理队列的下溢和上溢的情况：packagemainimport"fmt"typeQueuestruct{elements[]interface{}}......
  • 10月4日总结
    在deepin23上编译gcc13.2deepin20素以软件版本过老被人诟病，换成最新的deepin23之后情况大有好转，但是gcc版本为11.2，鄙人对此仍有意见，所以特意研究了如何编译一份较新的gcc来用。1.下载源码包http://mirrors.ustc.edu.cn/gnu/gcc/我相关在中科大镜像站下载东西，选择13.2版本的压......
  • pta三次实验的总结
    第一次pta作业 在pta第一次作业，因为是第一次作业所以大体是比较容易，但是也有几个要注意的点，就是两个double的值相加减相乘的值与实际值会有一定的误差，误差大小为0.0000001,所以在写pta的三角形的判断类型的时候会有等腰三角形测试答案错误，不能通过测试点，但是在测试直角三角形时......
  • 10 月 5 日模拟赛总结
    #Before[本文章在博客园同步发布]()[Contest-Link](https://www.luogu.com.cn/contest/137474)预期$100+100+5+0=205$。实际$0+100(0)+5+0=105(5)$。（括号是重测前）挂分$200$。rk21，直接垫底。~~菜死了~~为什么会挂$200$呢？且听下文分解。#T1##Description......
  • 【图论】【寻找性质】CF1151E Number of Components 题解
    CF1151E发现每一个\(f(l,r)\)中的连通块总是一条链（一棵树）。那么此时连通块的数量就等于点的数量减去边的数量。先考虑点的总数，一个价值为\(a_i\)的点一定是在\(l\leqslanta_i\)且\(r\geqslanta_i\)的\(f(l,r)\)中才会有一个贡献，根据乘法原理，它会产生\(a_i\time......
  • 前端代码格式化规范总结
    在日常开发过程中，经常会碰到代码格式化不一致的问题，还要就是js代码语法错误等没有及时发行改正，下面就介绍一下如何使用eslint、prettier、husky、lint-staged、commitizen来规范代码格式和提高代码质量的方法。目录准备工作代码检测代码格式化Git规范准备工作新建项......
  • 2023.10.5——每日总结
    学习所花时间（包括上课）：0h代码量（行）：0行博客量（篇）：1篇今天，上午学习+休息，下午学习+休息；我了解到的知识点：1.Maven；2.SpringBoot；明日计划：学习+休息......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99