一些概念
连通分量 :无向图中,满足任意两点之间都有路径相连的极大连通子图.换而言之,抽离出一些点以及它们之间的边,满足这些点任意两点之间,可以直接或间接到达对方,在这个前提下,抽离出的图越大越好,把抽离出的图叫做连通分量.
割点 :无向图中,删除该点及与其相连的边后,图的连通分量数量增加的点.换而言之,删除一个割点及相关边后,图中原来连通的两点不再连通,从而使得一个连通分量分裂成两个(或多个)连通分量.
点双连通 :若对于一个无向图,其任意一个节点对于这个图本身而言都不是割点,则称其点双连通.也就是说,删除任意点及其相关边后,整个图仍然属于一个连通分量.
点双连通分量 :无向图中,极大的点双连通子图.与连通分量类似,抽离出一些点及它们之间的边,使得抽离出的图是一个点双连通图,在这个前提下,使得抽离出的图越大越好.
边双连通分量 :其实就是求出来割边之后,对去掉割边的图遍历以下求出来所有的
Floyd算法
通过dp的方式进行转移, dp[i][j] 表示从i到j的最小边权和,枚举中间点k更新最小点权.
注意:floyd算法要枚举kij不是ijk
例题:一个人在图上1节点,每步可以走向与他相连的其他节点,也可以不动,还可以自爆,自爆之后就不能动了,求经过k步之后的所有行走情况和.
一些特殊情况的处理:
- 这一步不动: 自己给自己连边,形成自环即可.
- 自爆: 我们假想一个新节点0, 所有点和0连边,0不和任何点连边(自爆之后不能转移出去).
最后,套上矩阵快速幂板子即可.
dfs序 欧拉序
这俩的区别:前者是节点遍历到的时候只会统计一次,后者是来的时候统计一次走的时候再统计一次.
求解最小欧拉路/欧拉回路
朴素dfs会超时,考虑两次反转:
每个点能走的路直接走,最后在回溯的时候记录当前点,然后把整个栈倒序输出(也就是,如果提前到达终点,要在路径上加环,直到走完所有路径).
dfs生成树 Tarjan
不懂,抄板子.
关于技巧
中介点,反图反向边,线段树优化简图等,很多.
例题
好多牛之间存在爱慕关系,其中爱慕具有传递性,A爱B,B爱C的话A也会爱C.爱慕关系构成一张图,明星牛的定义是受到所有牛的爱戴(所有牛是爱慕自己的),求一张图有多少个明星牛.
因为满足传递性,我们要把图缩成一张DAG(有向无环图),此时 牛之间不会存在相互爱慕的关系 ,所以如果一个牛受到别人的爱戴,他不会再爱戴别人,所以直接统计出度是0的点即可,多个出度为0直接输出0(因为此时图不再联通).
有一个特殊的地图,首尾相接,上下相接,如果你能从起点走到无穷远处,可以认为走出迷宫,问你能不能走出迷宫.
dfs和vis.dfs记录四个参数:原始的坐标(yx)和取模在这张地图上的实际坐标.如果取模坐标一样但是实际坐标不一样,可以被认定存在一个环,必定有解.
可以用全局变量ff存储有没有解,方便每个dfs及时回溯.
二分图
点可以分成两拨,左边点会和右边点连线,左边点或右边点都不会有连向自己方的线的图.
例题
有一辆大巴车,每排能坐两个人,每个人有两个希望坐上的排数,请你给出最多能使多少人满足愿望.
如何解决一个点能匹配两个人的问题?
可以扩大点集,让人同时和a+n的点连线.这样就可以转换为一个二分图了,直接跑最大匹配就行.拓展:点能承受的个数变成 $f(n)$ 也能做,装到umap里就行.
网络流
- 最大流=最小割.
- 理论上可以算出割的点哪个属于哪个分支,但是我不会,碰到再说
- 计算最小割的最小割边有几条:类似CTF中的LSB隐写,我们对边权转换为 $w_i*P+1$ 的格式,P是一个大常数,然后高位是边权不影响网络流,低位存储边的信息,保证了最小割使用的是最小的边.
- 构造字典序最大的最小割边(没见过,不会)
网络最大流
尝试理解最大流中”w”的定义:流过一条边的最大剩余流量.如增加那么剩下的流量给到负权.
最小费用最大流
尝试理解”负环”的定义:初始时有一个全部剩余流量(flow)为正且权值(cost)均为负的环叫做负环.
网络流算法中回退边组成的负权环由于流量初始为0,不算负环.
网络流24题
一个环上有n个点,两个相邻点之间可以1代价转运一个重量为1的物品,问最少转运多少次能够全部点的物品数量一致.
s->环->t.
s->环,是他们的差值,代价是0.
环上的点:相互之间是inf的流量,代价是1.
环->t,差值,代价也是0.然后直接求费用流即可.
骑士共存问题:棋盘上有一些格子能放马(中国象棋的规则,能够攻击日字形的棋子),问你一个棋盘上能放多少个互相不攻击的马.
网络流.注意到日字不包含一个点对角线上的点,考虑染成国际象棋一样的黑白,然后不互相攻击就是求最大独立集(任意两点之间没有边相连),我们有:
最大独立集=能放马的点数-最大匹配.
对于二分图,由于可以分成黑白两部分,所以可以直接跑网络流.
而对于更一般的图,由于找不到合适的源汇点,最大流跑二分图是解不出来的.
一般图的最大独立集是NP-Hard.具体地,s与黑点连1边,黑点往能攻击到的白点连inf边,白点往t连1边,然后跑最大流(最小割).
启示:实际上黑白这就是个二分图,跑一下最大匹配应该也行.