7/18 图论 P1
小组成员：吴予涵、郑荣、林育辰、许文博、刘天顺。
压位高精除法
在普通高精存储数位过程中，由于 a_i 的每一位是整型，故存在浪费。
而在压位高精除法中，a_i 存储 8 个整型。在 12'34567890 中，a_1 = 12, a_2=34567890。
计算时，首先让 a_i 与 b_i 相加，若大于 1e8 则进位，则 a_{i - 1} 与 b_{i - 1} 相加的结果需要加上上一位进位，以此类推。
图论 P1
基本概念
点的度数：点连接的边数。
自环：一条边的两端点是同一个点。
途径：可以经过相同的边，经过的边数是途径的长度。途径可以是有限或无限长度。
迹：不经过相同的边的途径。
路径：不经过相同的点的途径。
完全图：任何两点之间都有边的无向图。
竞赛图：任何两点之间都有边的有向图，方向不定。
导出子图：选出的点若有边，则在导出子图中一定有边的子图。
补图：原图中两点若无边，则在补图中一定有边的图。
二分图：可以被分成两个部分，各部分内部没有连边，只有部分和部分之间有连边。
树：n 个点，n - 1 条边的连通图。
环：n 个点，n 条边的无向连通图。
基环树：一棵有 n - 1 条边的树加一条边得到的树。
链：首位相接的特殊的树。
菊花图：以一个点为中心散射 n - 1 条边连接其它点的特殊的树。
存图
邻接矩阵、邻接表（把一个点连着的边都用一个 vector 存起来，每个边具有一个指针，指向点连着的下一条边）。
链式前向星：struct 存边，存储 $to$（边的端点），$next$（下一条边），$val$（边权）
存储
struct edge {
int to;
int next;
int val;
} e[MAXN];
int head[MAXN], eid;
void adde(int x, int y) {
eid++; // 累加边的编号
e[eid].to = y;
e[eid].next = head[x]; // 下一条边是原先由 x 出发的第一条边，更新该边的属性
head[x] = eid;
}
查询（遍历从点 u 出发的所有边）。
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
...
}
最短路算法
Floyd（多源最短路）
dis_{i, j} 记录的是 i 到 j 的最短路。
if (dis[i][j] + dis[j][k] < dis[i][k]) dis[i][k] = dis[i][j] + dis[j][k];
Dijkstra（单源最短路）
适用于没有负环（权值之和为负的环）的图。
d_x 记录源点 s 到 x 的最短距离。初始时 d[s] = 0，其他点的 s 为 +\infin。
每次选取未选过的 d_x 最小的点 x。
if (d[v] > d[u] + W_{u, v}) d[v] = d[u] + W_{u, v};
SPFA
死了。
可以用于含负权边的图的最短路，可用于寻找负环（若一点入队超过 n 次，则有负环）。
初始化和存储类似于 Dijkstra。每当一个点的最短距离被更新则将其加入队列，每次取队首尝试松弛与其相连的的点知道队列为空。
if (d[v] > d[u] + W_{u, v}) d[v] = d[u] + W_{u, v}; // 松弛
差分约束（P1993 小 K 的农场）
已知一组关于变量差的限制不等式，每个不等式确定两个变量差的最大值，求某两个变量 t, s 之差的最大值可能是多少。
对于所有形如 x- y \le v 的不等式，记 y 到 x 有一条边权为 v 有向边。
最短路计数
设当前点 u，相邻点 v，边权 w。若 d_u + w < d_v 则 f_v = f_u。若 d_u + w = d_v 则 f_v 加上 f_u。
P2294 狡猾的商人
114514
飞行路线
核心代码：
if d[v][i] >= d[u][i] + w d[v][i] = d[u][i] + w;
if d[v][i] >= d[u][i - 1] d[v][i] = d[u][i - 1];
【重要的】城市
核心代码：
if f[i][j] == f[i][k] + f[k][j] p[i][j] = 0;
P3110 [USACO14DEC] Piggy Back S
P > B+E 则不合体，否则合体。对 B、E、合体点分别进行 Dijkstra。
T 个点的无向图，求从 S 到 E 恰好 N 条边的最短路
d_{i, j, m} 表示从 i 到 j 经过 t 条边的最短路。d_{i, j, m} = \min(d_{i, j, m}, d_{i, k, m - x} + d_{k, j, x})。输出 d_{S, m, N}。