A
给一些点和边，询问两点之间的最短路，直接 $floyd$。注意是无向图还有格式。
B
给出一些点的横纵坐标，求最小生成树。先预处理出两点之间的距离，然后直接跑一遍 $Prim$。
C
给一些点和边，有边权。询问两点之间路径上面最大的边的权值是多少。点很少，直接 $floyd$，把转移式子改一改就好了。
$f[i][j]$ $=$ $min(f[i][j]$, $max(f[i][k], f[k][j]))$
D
给一些点的坐标，两点之间的边权就是两点之间的距离，一开始有一边是选中的，要让你选一些剩下的边使得所有点连通且边权和最小。对于那些一开始选中的边，像 $Kruskal$ 过程中那样，计算出哪些点已经连通了，还差多少边。然后跑一下 $Kruskal$ 就做完了。
E
跟 $D$ 题有点像，大概就是求一下有 $m - n$ 个点的最小生成树是多少，$Kruskal$ 就完事了，点貌似还不要求连通。
F
让你把一个全部位置都有 $bug$ 的状态变成没有 $bug$ 的状态，从一个状态变成另外一个状态有对应的费用，然后要让花费最小。
从状态 $x$ 变成状态 $y$，对于 $x$ 状态，$0$ 表示不用管这个位置是什么，$-$ 表示这个位置没有 $bug$, $+$ 表示这个位置有 $bug$；
对于 $y$ 状态，$-$ 表示这个位置没 $bug$，$+$ 表示这个位置有 $bug$。
考虑最短路，我们发现如果预处理出所有状态的后继状态复杂度太高，但是我们可以在跑最短路的过程中枚举后继状态，因为只有题目给出的后继状态是合法的，而且不多，故枚举，$dij$ 然后就完事了。
可以参考算法竞赛入门经典
$P$ 365 例题 11-6
G
题意就是给你一个无向图，有边权，走多趟从 $s$ 走到 $t$，要求每一趟的人数不能超过走的路径的最小边权，求最小需要走多少趟。
考虑用 $floyd$ 处理出从 $s$ 走到 $t$ 每一条路径中边权最小值的最大值，就能很容易求出答案了。
$f[i][j] = max(f[i][j], min(f[i][k], f[k][j]))$
答案就是： $d / (f[s][t] - 1) + (d \% (f[s][t] - 1) != 0)$
$-1$ 是因为每一趟导游也要跟着走。
H
题意大概是给一些电梯还有他们可以达到的楼层，还有各自移动一层所需要的时间，从一个电梯到另一个电梯需要花费 $60 s$，问你从 $0$ 层到 $m$ 层最少需要多少时间。可以这么建图，同一个电梯之间的楼层相互连边，边权就是 楼层差 $\times$ 一层需要的自动时间 。然后不同电梯可达同楼层之间相互连一条边权为 $60 s$ 的边，然后就可以跑最短路了。然后我们发现其实点很少只有 $100$ 个，大力上 $floyd$，同电梯先跑，然后再跑不同电梯，答案就是 $f[0][m]$。
I
一个 $dij$ 模板题，注意是无向图。
J
一个 $spfa$ 判负环的模板题。
K
差分约束，发现相加是连续的，所以可以表示成前缀和的形式，所以就愉快的跑个最短路就可以了。
$s_i + s_{i+1} + s_{i + 2} + … + s_j = sum_j - sum_{i-1}$
$sum_j - sum_{i-1} > w$
$sum_j - sum_{i-1} < w$
L
给出货币之间的汇率，问你是否存在一种方案，使得货币经过若干次转换之后再转换回来，钱变多了，输出转换次数最少的方案。考虑 $dp$，$dp[i][j][k]$ 表示 $i$ 货币转换成 $j$ 货币 $k$ 次时最大的汇率。然后跑 $floyd$ 来转移，当 $dp[i][i][k]$ 大于 $1.01$ 就可以输出了，路径记录就是记录转移时的 $j$。
$f[i][j][p + 1] = f[i][k][p] \times f[k][j][1]$
$path[i][j][p + 1] = k$
M
一个有向图，求一个点到另外一个点有多少不同的路径。$dp[k][i][j]$ 表示从点 $i$ 到点 $j$，路径长度为 $k$ 有多少条，然后你会发现其实转移就是一个矩阵乘法，每跑完一次矩阵乘法就是完成了一个 $k$ 的统计，把结果加到答案矩阵中。对于那些有环的，我们可以发现路径长度最长就只有 $n$ ，就是一条链的情况，那么我们就可以把那些 $k > n$ 的时候答案非 $0$ 的记录一下，那些就是有环的点。
$f[r][i][j] += f[r - 1][i][k] * g[k][j]$
$g$ 表示的是一开始的矩阵，$i$ 和 $j$ 之间有一条边 $g[i][j]$ 就为 $1$。$f$ 就是上面的 $dp$ 。
（不知道空间够不够，反正我滚动了
N
给出每个点的坐标，两点之间的边权就是两点之间的距离，要求找出一条路径上的边权没有大于 $10$ 的最短路径最长的路径。对于那些两点之间的距离大于 $10$ 的点对，把他们之间的边权置为 $INF$，然后跑个 $floyd$，最后对点对之间的最短路径取 $max$ 就可以了。
O
给一些点，每个点有容量，一些生成能量的点，和一些汇聚能量的点，问这些点最多能够吸收多少能量。最大流的模板题了吧。首先超级源点向所有生成能量的点连一条容量为 $INF$ 的边，所有汇聚能量的点向超级汇点连一条容量为 $INF$ 的边，然后因为有点容量，所以我们要拆点，然后同个点之间连一条容量为点容量的边，然后其他的点该怎么连怎么连，跑个最大流就完事了。
P
题意就是给一个无向图，起点 $s$，终点 $t$ ,让你求一个从 $s \rightarrow t \rightarrow s$ 的最短路。
首先来举个例子来说明为什么跑 $s \rightarrow t$ 的最短路记录访问再跑 $t \rightarrow s$ 不行。
（中间那条边边权是 $1$，忘记写上去了）
那么怎么做呢，考虑最小费用最大流，因为我们是要求$s \rightarrow t \rightarrow s$ 的最短路，可以看成是 $s$ 两次到达 $t$ 的最短路。
所以我们可以这么建图，两点之间有路径的建一条容量为 $1$，费用为两点边权的边，容量为 $1$ 保证这条路径只能访问一次。然后源点向 $s$ 连一条容量为 $2$ ，费用为 $0$ 的边，因为是无向图，而且我们把求答案的过程看成是 $s$ 两次到达 $t$，$t$ 向汇点连一条容量为 $2$，费用为 $0$ 的边。
图建完之后就跑个最小费用最大流，如果汇点的最大流不是 $2$，说明不存在，否则最小费用就是答案了。
注意是无向图，所以连边的时候要正反都连。
Q
这就是一道计算几何题，不知道为什么放到图专题里面来。。。
题目就是顺时针或者逆时针给你一些点的坐标，这些点能构成一个多边形，问你这个多边形内角最大的角是多少。
注意题目没有跟你说是顺时针还是逆时针，而且也不一定是凸多边形。所以做这道题的时候先却定是否是逆时针（这里可以取右上角的点，然后看看左右的点孰高孰低），如果不是就把给出的坐标数组 $reverse$ 一下，然后判断内角是否大于 $180$ 度可以用叉积来判断。
然后写就是了。
R
给出 $n$ 种插座，$m$ 种设备和对应的插头，$k$ 种转接器第一个是插口，第二个是插头，每种转换器有无限个，相同字符串的插头和插座相互对应，问你尽可能多的把设备插上电后，最少剩多少设备不能插上电。
一眼就是最大流对吧？
那要怎么建图，首先源点向每个插座连一条容量为 $1$ 的边，每个设备插头向汇点连一条容量为 $1$ 的边。对于一个转换器，插头向插口 连一条容量为 $INF$ 的边，然后跑个最大流就完事了。
S
题意差不多是给你一个 $a \times s$ 的坐标图，还有 $b$ 个点的坐标，问你这 $b$ 个点是否能够各自规划出一条走到边界的线路，并且线路之间没有交点。
好，最大流。
源点向给出的 $b$ 个点连容量为 $1$ 的边，边界的点向汇点连一条容量为 $1$ 的边，然后坐标的点互联容量为 $1$ 的边，但是我们发现一个东西，就是这样有可能在拐角处相交，所以我们要把每个坐标点拆开来连一条容量为 $1$ 的边，这样把点变成边，就能保证每个点最多只被一条线路经过一次。
跑个最大流，如果最大流为 $b$ 说明存在。
T
题意是给你一个 $n \times m$ 的矩阵，表示 $G[i][j]$ 表示 i 警察到 j 银行需要的时间，问你要怎样安排每个银行一个警察，使得到达银行的总时间最少。
源点向警察连一条容量为 $1$ ，费用为 $0$ 的边，警察向每个银行连一条容量为 $1$ ，费用为 $G[i][j]$ 的边，每个银行向汇点连一条容量为 $1$，费用为 $0$ 的边。
$mincostmaxflow$，$done$.
U
这道题第一个样例输出是错的，应该是 $Impossible.$
这个最小费用最大流好裸的，题目已经给了你点对之间的容量和费用了，按照给的建就是了，有给定流量，就源点和 $1$ 连一条容量为流量的边，然后就做完了。
V
题意是给你若干个指环，有一些指环是用绳子连在一起的，现在让你选两个指环，然后把他们拉直，使得绷直的绳子最多，问你有多少被绷直的绳子。
把指环看成点，把绳子看成边，显然，选两个环然后被绷直的绳子的长度就是他们之间的最短路。
那么，我们就只需要枚举两点，然后再枚举点，看看是否是最短路上的点，是就计数（两点之间的最短路不止一条），然后更新答案，注意一下细节。
W
裸的一个并查集，写就是了。
X
给你 $n$ 种操作，一些操作是询问一些是表明关系，对于询问根据已给的关系输出 $0$ 或者 $1$ ，分别表示不知道和知道。对于表明关系的操作如果跟前面已表明的关系冲突，则输出 $-1$。
带权并查集（带权并查集学习），因为关系只有相同和不相同，那么就考虑 $0$ 表示和父节点相同，$1$ 表示和父节点不同，然后学完带权并查集后你就知道怎么做了，因为只有 $01$ ，所以向量操作的时候要 $\%2$。
Y
题意差不多是给你一个无向图，有边权，后 $B$ 个点是城堡，前 $A$ 个点是村庄，马里奥要从编号为 $n$ 的城堡营救公主后然后用最快的时间到达编号为 $1$ 的村庄。
马里奥有膜法靴，魔法靴最远能够跑 $L$ ，最多能使用 $K$ 次，特别的，马里奥能够直接穿越村庄而不用停下来，而城堡里有陷阱所以需要停下来。
考虑跑最短路，多一维记录膜法靴的使用状态 $dis[i][j]$ 表示从 $n$ 到 $i$ ，使用了 $j$ 次膜法靴的最短路径。对于可以穿越的村庄，我们可以先跑个 $floyd$ 把两点之间的最短路径处理一下，比如 $i \rightarrow k \rightarrow j$ 的距离小于 $L$，那么我们就可以 $f[i][j] = min(f[i][j], f[i][k] + f[k][j])$ ，否则 $f[i][j] = INF$，这样子就能城堡村庄一视同仁，方便转移了。
直接跑个 $spfa$ 就可以了。
Z
诡异的一道题，也是跟图毫不相关。
题意是每一头奶牛都有一个生产牛奶的周期，在周期内每天的产奶量都不同，如果在同一天有 $\ge$ 2 头最小产奶量相同的奶牛，那么 $John$ 就不吃牛，反之吃掉那头最小产奶量的奶牛。
所有奶牛的相同生产周期就是他们各自生产周期的 $LCM$ ，求完后直接模拟就可以了，当一个 $LCM$ 周期内没有奶牛被吃掉的话，以后就不会有奶牛被吃掉了，就可以直接输出答案。
然后就做完了。
专题总结：
总的来说题目还是比较基础，少数模板题，除了题目难读一点，输入输出格式诡异之外，这个专题还是一个补基础不错的专题。
收获就是巩固了网络流建图这方面的知识，还有复习了一下差分约束和并查集。
关于代码，我提交的代码都 $share$ 了，在这篇 $blog$ 就不贴上来占用空间了。