Day 4 丁明朔
（图的dfs和bfs是重点）
Pts 30：dfs两点之间的所有路径，若都相同，则可以，反之不行
Pts 100：图的性质：
图的dfs树，只有返祖边，无横叉边
先用dfs树（树边），然后再用非树边（返祖边）判断一下即可
LCA（最近公共祖先）代码
Dijkstra堆优化：
Pair第一个（first）存的是源点到当前点的最短路，第二个（second）是这个点的编号。
SPFA：
（最长路代码）
循环队列：
就是循环的，重复利用，尾指针到头时返回第一个
Floyd：
Kruscal：
最小生成树的最大边权一定最小
无向图的最小生成树
拓扑排序：（1.在拓扑序上进行动态规划2.判环）
首先我们肯定要二分（毕竟最大值最小）
边权大于mid的边权让其免费，小于的就会被抹掉
枚举之后，若最小值mid<=k则当前mid可行
就是把原图复制k份，形成一个三维的图形，同一层点之间的边权就是原图中的边权，相邻两层的点之间的边权都是零。然后dis[i][j]就表示在第j层、1~i的最短路，对于每一个点和其所在层数，有两种转移：1.转移到同层相邻的点 2.转移到下一层相邻的点。跑一个二维dijkstra（加堆优化）就好了。
（这个题面是真的鬼畜啊）
建一个过渡用的点，将所有点与其连接，跑一边最短路，答案为其一半
借助过渡点，可以实现两个点之间的互相转换
证明按照dfs树走最优，按照dfs树排序，求出两点之间的LCA，求两点之间的最短路
我们需要求出所插入点的前驱和后继，加边的时候应用类似于营业额统计
Tarjan
一些关于强联通的知识点在笔记本上
极大强连通子图叫做强联通分量（判环：1.拓扑排序2.tarjan）
若有一个子图，是强联通的，那么这些牛两两互相受欢迎
若一个图的每个强联通分量，若把他们看成一个点，则最后一定会没有环
DAG（有向无环图）【可以拓扑排序】
将强联通分量缩点后，若>1个点无出边，则他们互相不符，若=1个点那么，强联通分量的大小就是答案
一个强联通分量是一个dfs树上的一块
dfn[i]表示一个时间戳
low[i]表示当前节点及他子树的出边所能连到的所有dfn中最小的一个
若一个点的low与他的dfn相同,则这是一个强联通分量
当我们找到一个强联通分量时,我们将这个点从图中拿去.
用栈来实现,我们每搜索一个点,我们将其入栈,在栈中找low,若low=dfn,则出栈(出栈到这个low=dfn的点为止,一起出栈的点是一个强联通分量)
按g从小到大排序，枚举g0，用所有小于g0的s边，做最小生成树，求最小值【但是会TLE】
当我们在连一条新边时，在该环上找到最大边删掉（连通性不发生改变），总复杂度O(mn)
求平面图的最小割，即求对偶图的最短路
对偶图：边变成点，点变成边，平面图的每一个块变成一个点，每一条边变成垂直的一条边
将每个强联通分量求出来
从点1开始跑一边最长路的spfa，就能求出1-n的所有利润，在酒吧的时候取max
倍增Floyd（这题数据点数M<=100,边数<=1000000）
g1[i][j]表示由i到j只经过一条边的最短路
g2[i][j]表示由i到j只经过两条边的最短路
然后通过取min得到
Floyd快速幂
除了最短路的点全部删除
匈牙利算法：
bool find
https://blog.csdn.net/sunny_hun/article/details/80627351
二分图，二部图
增广路径（就是完成配对的过程）
就是匈牙利算法的裸版子了吧qwq
差分约束做法，最长路