主要记录一些将要学习的图论知识，或者概念还不是很清晰的图论知识。
个人感觉有关图论的竞赛知识基本上已经学完了，下面就是如何的灵活运用qaq.
二分图的多重匹配
二分图的多重最大匹配(边数最大)
建立相应的模型，然后跑最大流
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值的边，每个Y方点向T连一条容量为该Y方点L值的边，原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），求该网络的最大流，就是该二分图多重最大匹配的值。
二分图的多重最优匹配(边权和最大)
使用最大费用最大流
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值、费用为0的边，每个Y方点向T连一条容量为该Y方点L值、费用为0的边，原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），费用为该边的权值。求该网络的最大费用最大流，就是该二分图多重最优匹配的值。
欧拉回路
无向图的欧拉回路
所有的点的度数都为偶数。
有向图的欧拉回路
所有节点的入度等于出度
混合图的欧拉回路
设一个节点D[i] = (out[i]-in[i]).
- 若D[]中存在奇数，那么一定不会存在欧拉回路。因为改变任意一条无向边的方向，D[i]的奇偶性不会改变。
- 若都是偶数，那么需要跑最大流，具体的说明见kuangbin模板的说明
若初始D值都是偶数，则将G’改装成网络：设立源点S和汇点T，对于每个D[i]>0的点i，连边
欧拉路径（不需要回到原点）
无向图的欧拉路径
有以下两种情况存在
- 所有节点的度数都是偶数
- 仅存在两个节点的度数为偶数，其它节点的度数都是偶数
有向图的欧拉路经
依旧有两种情况
- 所有节点的入度等于出度
- 仅有两个节点：一个节点的入度比出度大1，另外一个节点的入度比出度小1. 其余的入度等于出度。
混合图的欧拉路经
如果存在欧拉回路，一点存在欧拉路径了。否则如果有且仅有两个点的（出度-入度）是奇数， 那么给这个两个点加边，判断是否存在欧拉回路。
曼哈顿最小生成树
2-SAT
二分图的匹配以及各种等价的形式
看西工大的ppt和毛老师的ppt
三种最大流复杂度的比较以及适用的范围
刷完24题，虽然很早之前就已经立下了这个flag
边双联通分量的求解
加入最少的边，使得图变成边-强联通分量
一个有桥的连通图，如何把它通过加边变成边双连通图？方法为首先求出所有的桥，然后删除这些桥边， 剩下的每个连通块都是一个双连通子图。把每个双连通子图收缩为一个顶点，再把桥边加回来，最后的这 个图一定是一棵树，边连通度为 1。 统计出树中度为 1 的节点的个数，即为叶节点的个数，记为 leaf。则至少在树上添加(leaf+1)/2 条边，就能 使树达到边二连通，所以至少添加的边数就是(leaf+1)/2。具体方法为，首先把两个最近公共祖先最远的两 个叶节点之间连接一条边，这样可以把这两个点到祖先的路径上所有点收缩到一起，因为一个形成的环一 定是双连通的。然后再找两个最近公共祖先最远的两个叶节点，这样一对一对找完，恰好是(leaf+1)/2 次， 把所有点收缩到了一起。