immix's blog

在阅读本文前，请确认你掌握了割点和桥的求法，否则请先阅读 连通性问题（2）- 割点和桥。 概念 仿照强连通分量，我们来定义边双连通分量和点双连通分量。 边双连通分量：原图的一个极大边双连通子图。 点双连通分量：原图的一个极大点双连通子图。 边双连通分量 洛谷P8436 【模板】边双连通分量 边双连通分量求解十分简单。只需把原图中的所有桥删去，在新图上所求得的连通分量就是边双连通分量。 求边双连通分量可以使用并查集或 dfs 求连通分量。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include<bits/stdc++.h>using namespace std;const int N = 5e5+5;struct Edge{ int u,v; b ...

概念 割点、桥是在无向图中的概念。 割点：删除节点 uuu 后，原图变为不连通，则称 uuu 为割点。 桥（割边）：删除边 (u,v)(u,v)(u,v) 后，原图变为不连通，则称 (u,v)(u,v)(u,v) 为桥。 点双连通：不存在割点的无向图称为点双连通图。 边双连通：不存在桥的无向图称为边双连通图。 一张点双连通图不一定是边双连通图，割点之间的连边不一定是桥，桥的起点和终点也不一定是割点。 割点 我们来考虑如何修改 Tarjan 算法求割点。 如上图，对于节点 uuu 来说，若存在 uuu 的子节点 vvv，使得 lowv≥dfnu\text{low}_v\geq\text{dfn}_ulowv​≥dfnu​，则 uuu 为割点。（因为从节点 vvv，无法回到 uuu 的父节点，则删除 uuu 后，vvv 与图其余部分不连通） 但对于根节点来说，这个判断是错误的。考虑只有一个子树的根节点。此时删除根结点后，原图仍然连通（本质即上文中图其余部分不存在了）。因此，对于根节点，我们需要判断子树数量。若子树数量多于一个，则根节点为割点，反之则不是。 桥 首先，桥一定是树枝边 ...

概念 强连通：有向图 GGG 中，任意两个节点互相可达。 强连通分量 (Strongly Connect Componet,SCC)：原图的一个极大强连通子图。也就是说，一个强连通分量是 强连通的：强连通分量内任意两个节点互相可达 极大的：不存在节点 u′u'u′，使得强连通分量加入 u′u'u′ 后仍然是一个强连通子图。 缩点：如果我们把每个强连通分量中的所有点看成一个点，就构成了一个 SCC 图。这个图一定不会存在有向环，因此是一个 DAG。 如上图左，节点 1、4 单独构成一个 SCC，节点2、5，节点3、6，节点7、8、9、10、11、12 构成了三个 SCC。缩点后得到新图如上图右所示。可以观察到，确实是一个有向无环图。 Tarjan 算法 Tarjan 算法可以在 O(V+E)O(V+E)O(V+E) 的复杂度下，通过一次 DFS 找出一个图的所有强连通分量。另外，Tarjan 算法还可稍加修改，用于求解割点、桥、双连通分量问题。 在讨论 Tarjan 算法之前，我们先了解搜索树。在对有向图进行 DFS 时，会形成一颗搜索树。每次搜 ...

DAY-1 省选前基本没有复习，都在做其他事情。最后周五晚上开了虚拟机想写点板子，结果也没写动，就写了个 A+B。不过把 NOI Linux 2.0 好好试了试，最后在考试前十个小时发现还是 Code::Blocks 最好用（只有CB有补全）。 DAY1 提早了三刻钟到，站了半个小时，然后在要进考场的时候看到了xpt（）。进了考场，老师说 Linux 和 Windows 都可以随便选，四周环视了一圈，都是用 Windows 的，不过我还是用了 Linux。打开 Code::Blocks 的时候没找到哪里调编译选项，调了 5 分钟。 T1 一开始不会做，思考了 x=1x=1x=1 的部分分之后想出来了。期望得分：100分。 T2 图论题，不会做，只会枚举每条边是不是新增的然后判断。复杂度 O(n2m)O(n2^m)O(n2m)，期望得分：10分。 T3 背景是一棵树，打一个贪心和一个链的特例，期望得分：36分。 DAY2 T1 不会做，只打了第一个特例。期望得分：20分。 T2 感觉和CF某题很像，打了40分部分分。 T3 完全不会，只能输出1。期望得分：2分。 总期望得分 100+10 ...

介绍 拓扑排序可以将一个有向无环图（DAG）的节点进行排序，排序后即可依次进行处理，使得排在前面的节点不能依赖于排在后面的节点，这样就可以满足 DP 的无后效性，进行 DP 求解某些问题。 Kahn 算法 Kahn 算法的步骤如下： 从图中入度为 0 的节点的集合中任取一个，并加入拓扑序； 删除该顶点和所有与其相连边； 重复 1-2 步，直到图中没有入度为 0 的节点。若此时图中还有边，说明图中有环。 如以下伪代码： \begin{algorithm} \caption{Kahn's Algorithm} \begin{algorithmic} \STATE $ L \leftarrow $ Empty list that will contain the sorted elements \STATE $ S \leftarrow $ Set of all nodes with no incoming edge \WHILE{$S$ \textrm{is not empty}} \STATE remove a node $n$ from $S$ \STATE ...

字符串 python 中，字符串（str）是一种不可变的序列结构。 字符串创建 定义字符串的方法有以下几种： 单引号、双引号 在 python 中，单双引号是完全等价的，在某些语言中，可能会区分字符和字符串，但在 python 中，字符就是长度为 1 的字符串。 12str1 = "Hello, world!"str2 = '114.514' 三引号 使用三个双引号或单引号可以创建多行字符串。三引号允许一个字符串跨多行，字符串中可以包含换行符、制表符以及其他特殊字符。 123mstr = """line1,line2,line3!""" 字符串转义 使用反斜杠可以转义字符。 转义字符 描述 ASCII码 \’ 单引号 39 \" 双引号 34 \\ 反斜杠 92 \n 换行 10 \t 制表符 9 123str1 = "line1\nline2"str2 = "He said, \"H ...

字典回顾 在Python中，字典是一个无序的、可变的数据类型，用于存储键(keys)和值(values)之间的映射关系。字典使用键来访问数据，与列表不同，不是使用索引来访问数据。 字典的主要特点包括： 字典由一系列键(keys)和值(values)组成，每个键映射一个值。 字典中的键必须是 不可变 对象，如字符串、数字、元组等，而值可以是任意对象。 字典是无序的，不支持索引，可以通过键查找值。 字典使用大括号{}来表示，每个键值对之间用逗号分隔。 字典是可变的，可以添加、删除、修改键值对。 字典长度可以使用内置的len()函数来计算，即键值对的个数。 字典操作 创建字典 12345#创建一个空字典my_dict = {}#带键值对的字典my_dict = {'name': 'John', 'age': 25, 'city': 'New York'} 访问字典的值 12my_dict['name'] #输出 ...

本篇文章中，存树的方式统一采用链式前向星。 链式前向星实现 12345678910int head[N];int nxt[N<<1],to[N<<1];int cnt=1;void add_edge(int u,int v){ nxt[cnt] = head[u]; to[cnt]=v; head[u]=cnt; cnt++;} 树链剖分的概念 将一棵树分割为若干条链，将维护路径问题转化为维护若干条链上信息。 我们介绍一种分割方式——重链剖分。 重链剖分可以将树上任意一条路径分割为 O(log⁡n)O(\log n)O(logn) 条连续的链，每条链上 dfs 序连续，因此可以采用线段树等维护路径上的信息。 对于重链剖分，给出一些定义： 重子节点：子结点中子树最大的节点。若有多个最大的，任意其一为重子节点。 轻子节点：剩余的子节点 重边：到重子节点的边 重链：若干条重边首尾相连形成重链。特别的，对于单个子节点，也认为是一条重链。 这样即可将整棵树划分为若干条重链。 实现 重链剖分通过两次 dfs 实现。 第一次 ...

最小割 最小割问题可以简单的这样描述：给定一张带权有向图，除去几条边，使 sss 到 ttt 不连通。求去除的边的权值和最小值。 形式化定义一下：对于图 G=(V,E)G=(V,E)G=(V,E)，将点划分为 SSS 和 T=V−ST=V-ST=V−S 两个集合，其中源点 s∈Ss\in Ss∈S，汇点 t∈Tt\in Tt∈T。我们定义割 (S,T)(S,T)(S,T) 的容量为所有从 SSS 到 TTT 的边的容量之和，即 c(S,T)=∑u∈S,v∈Tc(u,v)c(S,T)=\sum_{u\in S,v\in T}c(u,v)c(S,T)=∑u∈S,v∈T​c(u,v)，最小割问题就是求一个割，使得割的容量 c(S,T)c(S,T)c(S,T) 最小。 最大流最小割定理 最大流最小割定理：f(s,t)max⁡=c(s,t)min⁡f(s,t)_{\max}=c(s,t)_{\min}f(s,t)max​=c(s,t)min​。 即对于一个网络，其最大流与最小割在数值上相等。我们在处理最小割问题时，直接求最大流即可。 求割边数 洛谷P1344 [USACO4.4]追查坏牛奶Pol ...

概念定义 网络：带权有向图 G=(V,E)G=(V,E)G=(V,E)。 容量：边 (u,v)∈E(u,v)\in E(u,v)∈E 的权值，记作 c(u,v)c(u,v)c(u,v)。 源点、汇点： s∈v,t∈v,(s≠t)s\in v , t \in v ,(s\neq t)s∈v,t∈v,(s=t)。 流量：设 f(u,v)f(u,v)f(u,v) 满足 容量限制：对每条边流量不超过容量，即f(u,v)≤c(u,v)f(u,v)\le c(u,v)f(u,v)≤c(u,v) 斜对称性：每条边容量与其相反边容量为0，即f(u,v)=−f(v,u)f(u,v)=-f(v,u)f(u,v)=−f(v,u) 流守恒性：除源点和汇点，流入每个点的流量与流出每个点的容量相同，即 ∀x∈V−{s,t},∑(u,v)∈Ef(u,x)=∑(u,v)∈Ef(x,v)\forall x \in V-\{s,t\},\sum_{(u,v)\in E}f(u,x)=\sum_{(u,v)\in E}f(x,v) ∀x∈V−{s,t},(u,v)∈E∑​f(u,x)=(u,v ...