- 2024-07-23CF521E Cycling City 题解
Description给定一张\(n\)个点\(m\)条边的无向简单图。问图中能否找到两个点,满足这两个点之间有至少三条完全不相交的简单路径。\(n,m\le2\times10^5\),图不保证连通。Solution容易发现有解地充要条件是存在两个环有边交,考虑在dfs树上做这件事。注意到非树边一定
- 2024-07-20D. 网络攻防
D.网络攻防题意:一张无向图,求至多删除\(k\)条边使得图不连通的方案数。\(k\in[1,2]\)。首先考虑\(k=1\),答案即为无向图中的桥边。预计得分\(15\)分。对于\(m\le2\times10^3\)的数据,我们可以枚举一条边删除,求剩余图中的桥边数量,最后加上桥边数量即可。预计得分\(30\)
- 2024-07-13poj3417
poj3417题目其实很简单,如果知道树上差分是什么基本就是秒了。首先题面所说的,有\(n-1\)条边,保证两点之间只有一条简单路径,显然是树。剩下的边就是让这个树产生环的非树边。题面要求删除两条边,使之分为两部分,假如没有环状的结构,也就是没有那些非树边,就只需要随便删除一条边就可以
- 2024-06-13吉姆 102394 H
描述一个无向连通图,每个点\(u\)有点权\(w_u\),处在\(u\)点时可以花费\(w_u\)的时间去任何一个距离\(u\)最短路径边数不超过\(f_u\)的点。现在,从\(1\)号点出发,对于每个\(1\lek\len\),求出\(1\)到\(k\)需要的最小时间。\(n\leq200000\)\(m\leqn+50\)解决
- 2024-04-09桥
桥桥是如果从图上删去这条边会使得这张图不连通的边。有两种方法1在图上任意一个环的边都不是桥,其他的都是。应为如果删去,儿子段和父亲段就不可达了。2首先,不在DFS树上的边肯定不是桥。如果一条在DFS树上的边不是桥\(\to\)它的子树内没有一个节点可以通过多条非
- 2024-02-28cf1555f-solution
CF1555FSolutionlink分析一张图中的环,我们可以考虑把图表示为一棵生成树加上许多非树边。对于这题,我们考虑动态维护一片森林,在每次准备加一条边\((u,v)\)时:如果这条边加进去后与森林不形成环,那么它与图肯定也不形成环,那么直接加进森林中。如果这条边是森林的一条非树
- 2023-11-14[题解] CF1051F The Shortest Statement
TheShortestStatement给一张\(n\)个点\(m\)条边的无向连通图,保证\(m-n\le20\),\(q\)次询问求两个点间的最短路。\(n,m,q\le10^5\)。由于边数只比点数多20,所以如果我们建出这张图的一棵生成树,那么非树边至多有21条。那么现在两点之间的最短路就转化成了不
- 2023-09-24CF1857G Counting Graphs
题目链接考虑每条非树边的取值,显然不能小于等于该边与树边形成的环中的最大值(当然这条非树边也可以不存在),所以每条非树边的取值范围就是\(S-max(w)+1\)(\(+1\)的原因是该边可能不存在)。暴力枚举肯定会超时,考虑优化。发现\(kruskal\)算法获得最小生成树的过程中,按从小到
- 2023-09-18Tarjan
无向图的割点先给出几个定理:A:一棵树中的所有结点对于任意结点的可达性一致。记\(p(u,v)表示u和v可以相互到达\)。也就是说,如果G是一棵树,那么\(\forallu,v\inG,\forallk,p(u,k)\iffp(k,u)\)。B:一个无向图的DFS树中,对于任意一个非树边\((u,v)\),\(u,v\)一定有祖先孩
- 2023-08-29次小生成树
前言记录一下,顺便捋一捋思路。前置知识最小生成树\(\tt{Kruskal}\)树上倍增\(\tt{LCA}\)非严格次小生成树有一种贪心的做法,我们先得出该无向图的最小生成树,最小生成树上的边称为树边,反之为非树边。先可以得到一个定理,次小生成树与最小生成树一定只有一条边不同,也就是次
- 2023-06-24纯纯的随笔
1.有向图欧拉回路计数:欧拉回路与一颗\(1\)为根且非树边排列好的内向树形成双射。欧拉回路映射内向树:把最后一条边看做树边,剩下走过的看做非树边。内向树映射欧拉回路:能按顺序走非树边就先走非树边,最后走树边。于是答案是\(T_1d_1!\prod_{i=2}^n(d_i-1)!\),其中\(T_1\)是
- 2023-06-17无向图Tarjan浅谈
NoteTarjanPart1怎么做自己看书Part2为什么是对的证明:搜索树是一棵树由于每个节点都只会访问一次,回溯一次,故会访问(n-1)*2条边,只取访问时的边,即n-1条,可以构成树证毕。证明:在一个简单环上的一条边不可能是桥如果破除这条边,只能把环断成链,不会损坏连通性。证毕。证明
- 2023-04-23《综述图论中连通性及相关问题的一些处理方法》笔记
基本概念边/点割集:若边集\(E'\)使得割掉这些边之后\(u\tov\)不连通,则\(E'\)是\((u,v)\)的边割集。类似地定义点割集。边/点连通度:若任意\((u,v)\)的割集大小都至少是\(s\),则\(u,v\)是\(s-\)边连通的。类似地定义点连通度。Menger定理:\(u\tov\)的边连通
- 2023-04-11[PA 2020] Trzy drogi
pjudge题解虽然写了,但可能是bot写的,写的很不清楚。根据经典做法,搜出一棵dfs树,对非树边赋随机权值,树边权值为跨过它的所有非树边的权值xor。那割三条边能割开的条件就是:选三条边的一个子集,这个子集中的边权xor为0。也就是存在\(w_i=0\)或\(w_i\oplusw_j=0\)
- 2022-12-22[AHOI2005] 航线规划
[[AHOI2005]航线规划]([AHOI2005]航线规划-洛谷)首先是树的经典套路,依次删边\(\Rightarrow\)倒着加边然后问题就转化为了求两点间非环边的数量,且会不断加边一直缩点
- 2022-11-22生成树的一个小结论
对于一张图,若已经建出了一棵生成树,然后考虑一条非树边是否能够替换一条树边。结论就是一条非树边\((x,y)\),只能替换树上路径\((x,y)\)上的任意一条边。二级结论,可以免
- 2022-11-18NOIP模拟赛Day1
T1:算是一个小数学题,但是要一些大胆的想法,就是答案不会很大,直接暴力即可。PS:T1一般不会很难,如果感觉没思路可以尝试打表。T2:要求无权图最小环的数量,可以考虑环的求法,例
- 2022-11-15【题解】[模拟赛20221115] Tree
模拟赛20221115Tree|CQNK\(O(m*n*2^n)\)很好做,但是本题有更优秀的做法:在此记录复杂度\(O(n*2^n)\)的做法。考虑从后往前dp,设dp状态\(f_{s,0/1}\)分别表示在填
- 2022-10-22loj3885. 「eJOI2022」Bounded Spanning Tree
草稿:非树边\(u,v,[l,r]\)把\(u,v\)路径上所有边上界与\(r-1\)取个\(\min\)。剩下的边左端点排序后贪心,每次取右端点最小的一个元素。开始只考虑树边。当前加入一
- 2022-10-21一道校内训练题 (数列)
考虑一个naive的做法,按照以是否为红边为第一关键字,\(id\)为第二关键字,顺次给权值。容易发现这种做法是不优的,因为非树边有可能\(id\)较小并且对后面的红边没有影响。
- 2022-10-07边三连通分量
这东西显然比广义串并联图和cluster上的DDP不知道简单到哪里去了/fn首先回顾一下几个比较基础的定义:边连通度:两个点之间的边连通度就是它们之间的最小割大小,即,最小
- 2022-08-15在线动态图连通性
动态图连通性再这样下去要被自己蠢死维护一副图,支持\(\operatorname{link,cut}\),判断\(x,y\)是否在同一个联通块中最\(naive\)的就是每次双端\(\operatorname{b