图论学习从入坑信息学竞赛就开始了，到现在已经很久了，值得总结一下
梦开始的地方——最短路
世上本没有最短路，抄近道的人多了，便成了最短路
——众所周知，最短路常用算法有三种：Floyd，SPFA，dijkstra，每一种在不同情形下都有不同的作用，其中，①\(Floyd\)处理多源最短路问题，复杂度为\(O(n^3)\)，②\(SPFA\)处理（可以）有负权边的单源最短路，\(O(km\)~\(nm)\)，且可以判负环，③\(dijkstra\)处理无负权边的单源最短路问题，堆优化复杂度为\(O((n+m)logn)\)
话不多说，上题目
1.
题意：RT
做法：卡\(SPFA\)的优秀代表，这告诉我们尽量不要用\(SPFA\)，用堆优化的\(dijkstra\)即可
2.单元最长路径（保证一定存在）
题意：RT
做法：每条边取相反数，然后用SPFA
3.
题意：给一张无向边带权的图，求从1号点到\(n\)号点的最短路，可以使得\(k\)条路的边权变为0 \((k\leq 10)\),
做法：最短路的套路之一，分层图。由于\(k\)较小，将原图复制\(k\)次，分成\(k+1\)张图，分别表示当前剩余的免费次数，原图上的一条无向边对应相邻的图与图之间用\(0\)边连接，表示使用一次免费次数，每一层的\(n\)节点都要连接汇点\(T\)，从\(1\)号点出发跑最短路，\(dis[T]\)即为答案
4.
题意：给一张有向边带权图，求\(1\)~\(n\)的路径中长度\(\leq\)最短路\(+k\)的路径条数\((k\leq50)\)，有无数条输出\(-1\)
做法：由于最短路和\(DP\)的血缘很近，所以经常会带有\(DP\)的思路（或者就是一道DP题）。设\(f[ i ][ j ]\)表示\(dis(1,i)+mindis(i,n)<=mindis(1,n)+j\)的路径条数，如果走了一条边，边权为\(w\)，到达\(v\)点，则有
\(f[ i ][ j ]->f[ v ][ j+w+mindis(v,n)-mindis(i,n) ]\) ,由于原图有环，所以用上面的方法分层后拓扑排序即可，如果有\(0\)环，这个环一定没有入过队列，所以如果有点没有入队，且这个点可以到达（可以到达的意思是，存在一条满足题意的\(1\)~\(n\)的路径，且这条路径经过这个点），就输出\(-1\)本题也可以用记忆化搜索完成，原理相同
5.
同上面也是分层图，不过这道题加了简单的建图，是一道培养思维的好（shui）题
总结：最短路问题大多是：①技巧（如分层图、拆点、虚拟节点），②建图，考虑什么作为节点，怎么连边，③启发DP思路
图上树学——生成树
有些时候，树上容易解决的问题在无向图上难解，一般来说，通过最优性判断出任意两点之间仅需要一条路径.即是生成树问题
1.
题意：给一张无向边带权图，每次询问找出一条u到v的路径，使得路径上的最小边权最大
做法：在最大生成树上，两个点u和v之间的最小边最大（两点之间路径唯一，则是一棵树，假设此时还有一条更优的边，那么加上它之后成环，此时删掉一条环边使得图变成最大生成树一定是删除其他边，那么就构成了一个更大的生成树），在树上倍增即可
也可以用\(kruskal\)重构树来做
2.
存在有向边但不存在环的图求最小生成树，将相同高度的点分为同一堆，转换为多个无向图最小生成树和块与块之间的贪心
3.
保证图连通，且有多余边，去掉之后就变成了生成树
4.[water]
加尽量小的边，直到一个点到另一个点连通，如同kruskal的操作（显然我考试的时候连这么简单的都没有想出来）
总结：目前看来，最小生成树多出现在最优性问题和连通性问题上，关键词为“大”，“小”之类，还是要多刷题
SPFA的天堂——差分约束系统
由\(xi>xj+p\)，类比最短路中的\(dis[v]\geq dis[u]+e[i]\)，所以将这一条件变成j连i一条长度为p的边，即为差分约束
1.（模板）
题意：给n个区间，每个区间有且仅有一个1，其余全为0，求整个序列最多可能有的1的个数
做法：用\(x[i]\)表示\(1\)~\(i\)中的1个数，则对于约束区间\([l,r]\)
\(x[r]-x[l-1]\geq 1\)
\(x[r]-x[l-1]\leq 1\) 另外有\(x[i]-x[i-1]\leq 1\)连边跑\(SPFA\)即可（虽然会被卡要优化）
2.
题意：给定一些约束条件，分别是\(a_x+1= a_y\)和\(a_x \leq a_y\)，求a数组最多有多少个不同的值
做法：如果直接将点当作ai的话，无法求出答案，所以边\((x,y)\)表示\(a_x\)最多比\(a_y\)大的值，两种限制分别变成
①\((x,y)=-1,(y,x)=1\)
②\((x,y)=0\)由于图可能不连通，分每个联通块考虑，\(a_x\)比\(a_y\)大的数值受到两者之间最短路的约束，所以问题变成求最短路，如果有负环则无解，对每个连通块跑一次最短路，\(ans\)=每个连通块最长的最短路径+1（由于边权最多为1，所以肯定至少有路径长+1个点，容易证明存在一种方案将\(dis+1\)个值分给这些点）
这道题说明了差分约束不一定要用点直接表示状态（即第一题，用点直接表示答案），也可以用路径来表示两点间的相对关系
总结：差分约束的大小关系一般比较明显，设的未知量（点）一般和答案直接相关，而不一定用列出不等关系的项直接做未知量（点）
连通分量——tarjan算法
人如其名，\(tarjan\)算法主要解决连通性问题，其作用范围有：
强连通分量：有向图中，分量中的点互相可达，在不考虑分量中走法的情况（即一个点和多个点没有区别）下可以用于缩点。缩点后变为有向无环图（\(DAG\)），可以拓扑排序
边双连通分量：无向图中，分量中没有桥，即任意两点之间至少有两条边不重复路径，边双之间以桥连接。缩点后变成一颗树
点双连通分量：无向图中，分量中没有割点，即任意两点间至少有两条点不重复路径，一个割点可能存在在多个点双里面。将所有点向它所属的点双连边形成圆方树（待学习）
1.
题意：给一张有向图，可以逆行一次，求从1出发最后回到1的一条路径，且路径上点数的最大值
做法：显然一个强连通分量中的点要么同时选要么同时不选，所以先缩点使得图变成一个\(DAG\)，然后对于一次逆行机会，使用分层图，拷贝一份原图，两层图之间即用逆行边连接，\(ans=maxdis(color[1],color[1]+n)\),最长路问题用SPFA解决即可（color表示点对应的强连通分量）
这道题缩了点之后可以保证一条路径在上下两张图中包括的点不重复（为什么加上了逆行之后不会出现重复点？因为如果走了与之前相同的点，那么由于图是DAG而注定不能回到\(color[1]+n\)，\(DAG\)的优越性）
2.
题意：求一张有向图的最大半连通子图大小和数量，半连通图定义为图内任意两点间至少有一条单向路径的有向图
做法：强连通分量中任意两点间都有一条双向路径，是更强的条件，显然是半连通图。\(tarjan\)缩点之后图变成了一个\(DAG\)，可以证明最大的半连通图此时只可能是一条链（如果选出的半连通图带了一个分支，那么分支两边的点不能互相到达，如果分支两边连了边，就可以变成一条链），所以题目变成了求\(DAG\)上的最长链，拓扑排序\(DP\)一遍即可
3.
题意：给一张无向图，将一些点打标记，使得任意一个点消失后其他的点都可以到达至少一个标记点，求最少标记数量以及最少标记的标记方案
做法：先求出点双连通分量，那么分情况讨论：
①无割点，即该分量与世隔绝，为防止标记点消失，所以需要两个标记，有\(size*(size-1)\)种方案贡献
②有一个割点，即割掉这个点之后该分量与世隔绝，所以要在除了割点之外的任意一个点打标记（如果该标记点消失，则其他点可以通过割点到其他分量里面去），方案为\(size-1\) ③有两个及以上的割点，无论割掉哪一个，该分量里的点都可以到其他分量里面去，无需标记将方案贡献乘起来即为方案数
总结：\(tarjan\)只是图论中的一个工具，通常用于简化图的结构，再搭配其他算法解题，也有考察性质的题目（烦）