图论个人总结
遇到最短路，没有负边权，只写dij！！！
无向图建边注意：
如果要使用i^1来判断一对边，请务必将cnt的初值设为2(1)；最好不要设为-1，不然会在循环的时候忽略编号为零的边；
无向图找出所有的环
以P4151为例，
void dfs(int x, int fedge, int qz) {
vis[x] = 1, d[x] = qz;
for (ri i = head[x]; i; i = nx[i]) {
if (i == fedge) continue;
if (vis[v[i]]) {
if (v[i] > x) continue;
f.insert(d[x] ^ d[v[i]]^w[i]);
}
else dfs(v[i], i ^ 1, qz ^ w[i]);
}
}注意这两行的优化：
if (i == fedge) continue;
if (v[i] > x) continue;最大异或和路径
以P4151为例，
注意到我们可以先随便选取一条1到N的路径，然后考虑其他所有的环，注意到我们可以把这条路径异或上任意的环，所以我们求出所有的环，然后塞到线性基里即可；
部分参见暑假集训Day3,4
在BFS求多源最短路时，一定要建立一个vis数组，使一个点只被加入队列一次
while (!q.empty()) {
int x = q.front(); q.pop();
vis[x] = 1;
for (ri j = head[x]; j; j = nx[j]) {
if (vis[v[j]]) continue;
q.push(v[j]);
vis[v[j]] = 1;
d[v[j]][i] = d[x][i] + 1;
}
}代码倒数第四行
剩余系BFS
以P3403为例
注意事项：1.因为要开LL，所以inf不能设为int的inf；2.避免以上情况就是将初值设为-1，特判一下；3.h==1的情况要单独考虑；4.注意实际情况，如果
对于无向图，边的建立与节点信息有关
此类题，如果建立所有边，往往会MLE、TLE
以CF968C为例
给定一张无向图和节点，两个节点
为了保证时间复杂度，我们要优化dfs
我们不能枚举所有点对，因为
为了防止MLE，我们并不存边，而是每次遍历时临时产生边，然后dfs判连通性；
void dfs(int x) {
if (vis[x]) return;
vis[x] = 1;
if (c[x]) dfs(x ^ ((1 << n) - 1));
for (ri i = 0; i < n; ++i) {
if ((x & (1 << i)) && (!vis[x ^ (1 << i)])) {
dfs(x ^ (1 << i));
}
}
}差分约束系统
因为差分约束的实质是约束两个变量的差，而直接将变量相减往往没有意义，所以我们经常转化为前缀和相减；
一个无向图的点度数和一定是偶数
证明：一条边使度数总和增加2；
用路径覆盖无向图，使每边恰好经过一次，求最小次数
显然我们要用欧拉路来覆盖；一个欧拉路可以连接两个奇度数点，所以方法数就是：奇度数点数量/2；（奇度数点一定偶数个（why？看上面））
点双边双看8字图（是边双不是点双）
简单路径：不经过重点和重边
有向图Tarjan
有向图就不要在Tarjan的时候记录父节点并舍去了；
假如你是要看整张图是不是强连通，就只让出栈一次就好了；
void dfs(int x) {
low[x] = dfn[x] = ++cnt;
st[++tp] = x;
for (ri i = 1; i <= n; ++i) {
if (p[x][i]) {
if (x == i) continue;
if (dfn[i]) {
low[x] = min(low[x], dfn[i]);
}
else {
dfs(i);
low[x] = min(low[i], low[x]);
}
}
}
if (low[x] == dfn[x] && !ans) {
while (st[tp + 1] != x) {
--tp; ++ans;
}
}
}假如某题的空间并不紧张，就请把数组开大一点吧……
找树的直径，DFS明显快于BFS
树上差分方法
树上差分全部在节点上进行，最终通过从树根开始的一次DFS得到答案 ，求出一个点及自身的子树和；
①链差分：求 n 条链覆盖的边
将各个链的起点 S 与终点 T 的 Tag +1， Tag[LCA] −2 ，所有权值为 n 的节点和它们爸爸间的边即为答案
②点差分：求节点被链覆盖的次数
将各个链的起点 S 与终点 T 的 Tag +1 ， Tag[LCA] −1 ， Tag[Fa[LCA]] −1 ，每个节点的权值即为自己的答案；
DFS树无横叉边（即任何不在树上的线段都是在一个子树内的）
一张无向图，最少添加多少条边，使其有欧拉回路
求出每个点的度数
奇度数点需要连一条新边
仅有偶度数点的连通块需要连两条新边
答案为上面统计的新边数 / 2 （一条边可以满足两个需求）
一张无向图，给定一些路径，问(u,v)之间有没有被这些路径覆盖
显然，只要u或其子树能覆盖v或其子树上一点即可；
树状数组维护 DFS 序
DFS 遍历整棵树，递归进入 ? 时，扫描路线 (?,?)，把 ? 在 DFS 序上对应位置 +1
?,? 可直达，当且仅当 ? 子树中的节点使 DFS 序上 ? 对应区间的和发生了变化
有向图的Tarjan就不要记录父边了，有边就走
看Tarjan学习笔记
当边权与点权有关，且要按照从小到大的顺序加边时，不妨按边加而不是按点
例题：动物园：给出一张联通带点权无向图，规定两点间最短路径为路径上最小点权，求所有点对间最短路径最大值之和，注意每个点对会被正反计算两次；
Tarjan不要忘了bool ins[N]
一定要在更新low的时候判断ins=1，很重要，不然tarjan缩点会出锅；
比如这个例子：
搜索到红色点时，不能用红色边更新low，因为蓝色点已经成环；
HAOI 2016 旅行
s到t选择一条最大最小边权比值最小的路径；
枚举最小边权，不过，在求对应最大边权时，只需要像kruskal一样，从大到小加边，用并查集看什么时候s，t联通；并不需要跑最短路；
子图，生成子图和导出子图
所有的顶点和边都属于图G的图称为G的子图。
含有G的所有顶点的子图称为G的生成子图。
设V1是V的一个非空子集，以V1为顶点集，以两端点均在V1中的边的全体为边集的子图称为G的导出子图，记作G[V1]。
导出子图G[V\V1]记为G-V1，它是从G中删去V1中的顶点以及与这些顶点相关的边所得到的子图。若V1={v}，则把G-{v}简记为G-v，称为主子图。
在图1-13中，G1是G的生成子图，G2是G的导出子图，G3是G的主子图。
卡SPFA
网格图；
如果SLF？可以卡到2^N；
所以还是不要加奇奇怪怪的优化；
int n , m , i ;
n = T * 2 + 1;
m = T * 3;
printf("%d %d\n",n,m);
for (int i = 0 ; i <T ; i ++)
printf("%d %d %d\n",i * 2 + 1 , i * 2 + 2 , 0);
for (int i = 0 ; i <T ; i ++)
printf("%d %d %d\n",i * 2 + 2 , i * 2 + 3 , - ( 1 << T - i ));
for (int i = 0 ; i <T ; i ++)
printf("%d %d %d\n",i * 2 + 1 , i * 2 + 3 , -( 1 << T - i - 1 ));
二分图建图，一定要区分左右点，给它们不一样的标号
求LCA，一定要在x,y深度相同时，再同时往上跳，不然，只能跳较深的
合并两棵树，合并后树的直径的两端点一定是这两棵树的直径的4个端点中的2个
在拓扑排序时DP，如果限制起点，一定要将不经过起点的点设为-inf
以P3627抢掠计划为例，一定要初始化f为-inf；
求树上一条链，使得链的长度乘链上所有点中的最小权值所得的积最大
其中链长度定义为链上点的个数；
从小到大加边/点，用并查集合并两个子树，维护一个子树的直径；因为经过新加的这条边，使两棵子树合并，经过这条边的最长链，就是在两个子树里分别找延伸最长的链；根据树的直径的定义，最远的点一定在直径的端点；
这个题还有一个讨巧的办法：每次更新答案，直接用点权×新树的直径；因为：如果直径更新了，那么一定过这条边；如果没有更新，之前一定有更大的答案；
合并两棵树，合并后树的直径的两端点一定是这两棵树的直径的4个端点中的2个，枚举更新即可；
注意修改的顺序！！！
有向无环图的必经点与必经边
1.在原图中，按照拓扑序，求出S到每个点的路径条数；
2.在原图中，按照拓扑序，求出每个点到T的路径条数；
3.根据乘法原理：
对于一条有向边
对于一个点
因为f可能很大，需要取模，最好多重hash一下；
给定无向图，求两点间的所有路线中，最小边权的最大值
路线一定在最大生成树上，求出最大生成树+倍增LCA；
或者直接在求树时一起回答询问；
基环树求直径
找出所有的环：沿着一个点一直向下走，一定能走到环；
bool circle(int x) {
int rt = x;
fc[rt] = x;
while (!fc[xia[rt]]) {
pre[xia[rt]] = rt;
rt = xia[rt];
fc[rt] = x;
}
if (fc[xia[rt]] == x) { // 注意判断是否是这次遍历到的
int vv = xia[rt];
sum[vv] = 0; vis[vv] = -1; // 求出前缀距离，标记最小值
tot = 0;
cir[++tot] = vv; // 入队
while (rt != vv) {
cir[++tot] = rt;
sum[rt] = sum[xia[rt]] + len[rt];
vis[rt] = -1;
rt = pre[rt];
}
cirlen = len[vv] + sum[cir[tot]]; // 求出环的总长
return 1;
}
return 0;
}每棵子树进行简单的DP，同时更新答案；
沿一个方向，在环上的直径分类讨论：
1.
2.
给定一棵基环树，求出删去环上一条边后，直径的最小值
有可能直径不在环上；
给定一个n个点m条边的有向图，有k个标记点
要求从规定的起点按任意顺序经过所有标记点到达规定的终点，问最短的距离；
n<=50000，m<=100000，0<=k<=10
这个范围其实是不能状压的
进行多遍最短路，求出st,en,k个点互相的最短路；10!枚举；
两点的LCA为树的完整欧拉序（每经过点就记录）中，两点中间的最小编号
对于一个点与它lca最深的在它欧拉序最近两个之一（只记录进栈的欧拉序）
求LCA，用delta调整到同一高度比试探法快
给定一棵树，和一些树上的路径，询问x,y有没有在一条路径上
离线；有解当且仅当一条路线从x的子树出发，到达y的子树；考虑固定一个变量：dfs整棵树，树状数组维护区间和，?,? 可直达，当且仅当 ? 子树中的节点使 DFS 序上 ? 对应区间的和发生了变化（每遇到一条路径就在另一端+1）
平面图定理：必要条件：m<=3×n+6
！！！二分图
匹配数是边数
最小点覆盖=最大匹配
最大独立集=点数-最大匹配
二分图的最大团=补图的最大独立集
最小边覆盖=点数-最大匹配数=最大独立集
有向无环图的最小路径覆盖：
算法：把原图的每个点V拆成Vx和Vy两个点，如果有一条有向边A->B，那么就加边Ax−>By。这样就得到了一个二分图。那么最小路径覆盖=原图的结点数-新图的最大匹配数。
证明：一开始每个点都是独立的为一条路径，总共有n条不相交路径。我们每次在二分图里找一条匹配边就相当于把两条路径合成了一条路径，也就相当于路径数减少了1。所以找到了几条匹配边，路径数就减少了多少。所以有最小路径覆盖=原图的结点数-新图的最大匹配数。
对于所有无向图
关系1：给定图G = (V,E)无孤立点，则G的极大点独立集都是G的极小支配集。
关系2：G的点覆盖数 a与点独立集数 b满足： a + b = n。
关系3：G的边覆盖数 a与边独立集数 b满足： a + b = n。（边独立集数即匹配数）
无向图的最小边覆盖 = (二分图两边顶点数 - 二分图的最大匹配数)/2.
若在无向图中存在节点i，则将节点i拆为i1,i2，分别位于二分图的X部和Y部。若存在边
n个点的完全图的生成树个数为n^(n-2)
曼哈顿距离转切比雪夫距离
对于
曼哈顿距离：
切比雪夫距离
将每个点的坐标改为
则新图的切比雪夫距离为原图的曼哈顿距离；
切比雪夫距离转曼哈顿距离
CF1051F
给定一个无向图，其中
看到这张图，感觉除了一棵树之外剩不了多少边，于是：
我们先随便搜出一棵搜索树来，然后，对于每一条非树边，选择其中一端，跑Dij；
这样，对于每个点的答案，就是