循环不变量

循环不变量不是编程意义上的常量，它是一个在一次循环前后都不变的性质、属性。用来证明算法正确性。

其证明过程类似数学归纳法，数学归纳法分为两种，第一类（普通）归纳法和第二类（强）归纳法。

第一类：假设 P(k) 成立，能推出 P(k+1) 成立；则P成立。

第二类：假设对所有 1≤m≤k，P(m) 成立，能推出 P(k+1) 成立；则P成立。

相对于数学上，算法是有终止条件的，要显式的终止假设。

证明过程写成：初始化，归纳，终止三部分。

以插入排序为例。

循环不变量：每次迭代开始时，子数组 arr[1..i-1] 是已排序的，且包含原数组前 i-1 个元素。

初始化

  • 当 i=1 时，子数组 arr[1..0] 为空，默认有序。

归纳

  • 假设：第 i 次迭代前，arr[1..i-1] 已排序。
  • 动作：将 arr[i] 插入到 arr[1..i-1] 的正确位置（通过内层 while 循环）。
  • 结果：arr[1..i] 变为有序。

终止

  • 当 i = n+1 时，子数组 arr[1..n] 是整个数组，且已排序。

时间复杂度符号

符号 定义 数学表达 含义 示例
大O (O) 渐进上界（最坏情况） $$f(n)≤c⋅g(n)$$ 复杂度不超过 g(n) $$3n^2+2n+1=O(n^2)$$
大Ω (Ω) 渐进下界（最好情况） $$f(n)≥c⋅g(n)$$ 复杂度至少是 g(n) $$3n^2+2n+1=Ω(n^2)$$
大Θ (Θ) 渐进紧确界（精确阶数） $$c1⋅g(n)≤f(n)≤c2⋅g(n)$$ 复杂度等于 g(n) $$3n^2+2n+1=Θ(n^2)$$

然后需要记住主定理。

算法主定理（Master Theorem）是用于分析分治算法时间复杂度的一个重要工具，特别是适用于形如以下递归关系式的算法：

$$ T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n) $$

其中：

  • $ n $ 是问题的规模；
  • $ a \geq 1 $ 是子问题的数量；
  • $ b > 1 $ 是每个子问题相对于原问题的规模缩小因子；
  • $ f(n) $ 是划分子问题和合并解所需的时间（即非递归部分的时间复杂度）。

设： $$ T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n) $$

我们比较 $ f(n) $ 和 $ n^{\log_b a} $ 的大小关系（注意：$ \log_b a $ 是一个常数，由 $ a, b $ 决定），可以分为以下三种主要情况：

情况一：
如果
$$ f(n) = O(n^{\log_b a - \varepsilon}) \quad \text{对于某个 } \varepsilon > 0 $$ 也就是说，$ f(n) $ 增长得比 $ n^{\log_b a} $ 慢一些。

那么： $$ T(n) = \Theta(n^{\log_b a}) $$

情况二：
如果
$$ f(n) = \Theta(n^{\log_b a}) $$ 也就是说，$ f(n) $ 与 $ n^{\log_b a} $ 同阶。

那么： $$ T(n) = \Theta(n^{\log_b a} \log n) $$

情况三：
如果
$$ f(n) = \Omega(n^{\log_b a + \varepsilon}) \quad \text{对于某个 } \varepsilon > 0 $$ 并且满足正则条件（regularity condition）： $$ a \cdot f\left(\frac{n}{b}\right) \leq c \cdot f(n) \quad \text{对于某个 } c < 1 \text{ 且足够大的 } n $$ 也就是说，$ f(n) $ 增长得比 $ n^{\log_b a} $ 快一些，并且这个增长是“规则”的。

那么： $$ T(n) = \Theta(f(n)) $$

总结：

  • 如果 $ f(n) $ 较小（多项式意义上），就取主项 $ n^{\log_b a} $，对应情况一。
  • 如果 $ f(n) $ 和 $ n^{\log_b a} $ 差不多大，就多出一个 log，对应情况二。
  • 如果 $ f(n) $ 较大，并且满足正则条件，那它主导整个运行时间，对应情况三。

示例1：归并排序 $$ T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n) $$ 这里 $ a=2, b=2, f(n)=n $

计算： $$ n^{\log_b a} = n^{\log_2 2} = n^1 = n $$

因为 $ f(n) = \Theta(n) $，符合情况二，所以：

$$ T(n) = \Theta(n \log n) $$

示例2：二分查找 $$ T(n) = T\left(\frac{n}{2}\right) + \Theta(1) $$ 这里 $ a=1, b=2, f(n)=1 $

计算： $$ n^{\log_b a} = n^{\log_2 1} = n^0 = 1 $$

因为 $ f(n) = \Theta(1) = \Theta(n^0) $，所以也是情况二：

$$ T(n) = \Theta(\log n) $$

注意事项

  • 主定理不适用于所有递归形式。例如，像：
    • $ T(n) = T(n - 1) + f(n) $
    • $ T(n) = T(n/2) + T(n/3) + f(n) $ 这类无法直接使用主定理求解。

一类题目是求两个函数之间的关系，既可以用上面的定义，也可以使用下面极限的方法（可以洛它！） $$ \lim_{n \to \infty} \frac{f(n)}{g(n)} \begin{cases} = c & \text{implies } f(n) = \Theta(g(n)) \quad \text{if } 0 < c < \infty \ = 0 & \text{implies } f(n) = O(g(n)) \ = \infty & \text{implies } f(n) = \Omega(g(n)) \end{cases} $$

分摊分析时间复杂度

合计方法（Aggregate Method）

通过计算n个操作构成序列的最坏总成本，然后平摊到n个操作上。

下面我们以一个栈（Stack）支持三种操作为例进行说明：

  • Push(S, x)：将元素 x 压入栈 S。
  • Pop(S)：弹出栈顶元素。
  • MultiPop(S, k)：从栈 S 中最多弹出 k 个元素（如果栈中元素不足 k，则弹出所有元素）。

最坏情况下的单操作成本

  • Push(S, x) 的最坏成本为 O(1)。
  • Pop(S) 的最坏成本为 O(1)。
  • MultiPop(S, k) 最坏成本为 O(k)。

假设我们总共执行了 n 次操作，包括任意数量的 Push、Pop 和 MultiPop。

关键观察：

  • 每次 Push 往栈中加入一个元素；
  • 而每个元素至多只能被 Pop（或 MultiPop）弹出 一次。

也就是说： 不管我们使用 Pop 还是 MultiPop，在 n 个操作中，最多只能弹出 n 个由 Push 操作压入的元素。

总成本估计：

  • 每个 Push 成本是 O(1)，最多 n 次 → O(n)
  • 每个元素最多被弹出一次 → 所有 Pop 和 MultiPop 总共最多执行 n 次弹出操作 → O(n)

所以：

n 个操作的总成本是 O(n)，每个操作的 平均摊还成本为 O(1)。

替换法/递归树求时间复杂度

一、替换法（Substitution Method）

原理 替换法的思路是：假设递归式的解为某个函数形式（如 T(n) = O(n log n)），然后用数学归纳法来验证这个假设是否成立。 步骤

  1. 猜一个解 T(n) = O(f(n))。
  2. 用归纳法证明这个猜测对所有较小的 n 成立。
  3. 替换回递推式，验证是否成立。 示例：

递归式： $T(n) = 2T(n/2) + n$ 我们猜测解为： $T(n) = O(n \log n)$ 用归纳法验证： 归纳假设：假设对所有小于 n 的输入，成立，即 $T(n/2) \leq c(n/2)\log(n/2)$ 代入原式：

$$ \begin{aligned} T(n) &= 2T(n/2) + n \ &\leq 2 \cdot c(n/2)\log(n/2) + n \ &= c n \log(n/2) + n \ &= c n [\log n - \log 2] + n \ &= c n \log n - c n + n \ &= c n \log n - (c n - n) \end{aligned} $$

只要 $c \geq 1$，上式说明 $T(n) \leq c n \log n$，即猜测成立。

二、递归树法（Recursion Tree Method）

原理

递归树法通过画出递归的结构图，直观地看到每一层的计算开销，并将所有层加总，从而求出总的时间复杂度。

示例：

还是这个递归式：

$$ T(n) = 2T(n/2) + n $$

我们用递归树表示如下：

第一层：

  • 工作量 = $n$

第二层：

  • 两个子问题，每个大小为 $n/2$，每个消耗 $n/2$，总共 $2 \cdot (n/2) = n$

第三层：

  • 四个子问题，每个大小 $n/4$，每个消耗 $n/4$，总共 $4 \cdot (n/4) = n$

……

继续下去，每一层的工作量都是 n，而层数是：

$$ \log_2 n $$

然后求和总时间为：

$$ T(n) = n \cdot \log n $$

归并/快排

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

void quick_sort(int a[], int l, int r) {
    if(l >= r) return;

    int pivot = a[(l + r) >> 1];
    int i = l, j = r;

    while(i <= j) {
        while(a[i] < pivot) i++;//找到左边比pivot大的数
        while(a[j] > pivot) j--;//找到右边比pivot小的数
        if(i <= j) {//此处分为两种情况理解，小于的时候正常交换，等于的时候i和j都是pivot的下标，所以i++，j--，退出循环。
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    if(l < j) quick_sort(a, l, j);//只要理解上面<=的意思，这里就很好理解为什么是l到j和i到r了。
    if(i < r) quick_sort(a, i, r);//此时i - 1和 j + 1是pivot的下标，所以不用再次排序。
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void merge_sort(int a[], int l, int r) {
    if(l >= r) return;

    int mid = (l + r) >> 1;
    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);//注意好地板除mid，划分好范围
    
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(a[i] < a[j]) {
            tmp[k++] = a[i++];
        }else {
            tmp[k++] = a[j++];
        }
    }
    while(i <= mid) tmp[k++] = a[i++];
    while(j <= r) tmp[k++] = a[j++];
    for(i = l, j = 0; i <= r; i++, j++) {
        a[i] = tmp[j];
    }
}

然后快排变形成找前k小的元素

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

void quick_select(int a[], int l, int r, int k) {
    if (l >= r) return;

    int pivot = a[(l + r) >> 1];
    int i = l, j = r;

    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            std::swap(a[i], a[j]);
            i++;
            j--;
        }
    }

    int leftCount = j - l + 1; // 左边元素个数

    if (k <= leftCount) {
        // 前k小元素都在左边
        quick_select(a, l, j, k);
    } else if (k > leftCount + (i - j - 1)) {
        // 需要左边 + pivot重复个数 + 部分右边
        quick_select(a, i, r, k - (i - l));
    }
    // 否则刚好包含左边 + pivot重复的部分，不需要再处理
}

动态规划

考试既可以用伪代码，也可以用正常的，所以下面全都用c++写

装配线调度

定义：

对于 i = 0 or 1，一共n个工序

$S_i[j]$：第i个流水线的j个工序 $a_i[j]$：第i个流水线的j个工序的加工时间 $e_i$：进入第i个流水线的时间 $x_i$：退出第i个流水线的时间

目的：使得总加工时间最少

方程：(1-index) $$ f^* = \min{f_1[n] + x_1 , f_2[n] + x_2} \

f_1[j] = \begin{cases} a_1[1] + e_1, & j = 1 \ \min(f_1[j - 1] + a_1[j],; f_2[j - 1] + t_2[j - 1] + a_1[j]), & j > 1 \end{cases} \ f_2[j] = \begin{cases} a_2[1] + e_2, & j = 1 \ \min(f_2[j - 1] + a_2[j],; f_1[j - 1] + t_1[j - 1] + a_2[j]), & j > 1 \end{cases} $$ 代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 0-index
int assemble() {
    int f1[N], f2[N];
    // 初始化
    f1[0] = e[0] + a[0][0];
    f2[0] = e[1] + a[1][0];
    
    // 动态规划转移
    for (int j = 1; j < n; ++j) {
        f1[j] = min(f1[j - 1] + a[0][j], f2[j - 1] + t[1][j - 1] + a[0][j]);
        f2[j] = min(f2[j - 1] + a[1][j], f1[j - 1] + t[0][j - 1] + a[1][j]);
    }
    // 最优解
    return min(f1[n - 1] + x[0], f2[n - 1] + x[1]);
}

然后可能会涉及到构造答案，我们开个辅助数组L[]便于我们反向递归搜索。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

int assemble() {
    int f1[N], f2[N];
    // 初始化
    f1[0] = e[0] + a[0][0];
    f2[0] = e[1] + a[1][0];
    l[0] = (f1[0] <= f2[0]) ? 0 : 1;

    // 动态规划转移 + 记录路径
    for (int j = 1; j < n; ++j) {
        if (f1[j - 1] + a[0][j] <= f2[j - 1] + t[1][j - 1] + a[0][j]) {
            f1[j] = f1[j - 1] + a[0][j];
            l[j] = 0;
        } else {
            f1[j] = f2[j - 1] + t[1][j - 1] + a[0][j];
            l[j] = 1;
        }

        if (f2[j - 1] + a[1][j] <= f1[j - 1] + t[0][j - 1] + a[1][j]) {
            f2[j] = f2[j - 1] + a[1][j];
            // 可选：记录每个点来源
        } else {
            f2[j] = f1[j - 1] + t[0][j - 1] + a[1][j];
        }
    }

    // 返回最终结果，并决定最后从哪条线出来
    int res;
    if (f1[n - 1] + x[0] <= f2[n - 1] + x[1]) {
        res = f1[n - 1] + x[0];
        l[n] = 0; // 最后从 line 0 出口
    } else {
        res = f2[n - 1] + x[1];
        l[n] = 1; // 最后从 line 1 出口
    }

    return res;
}

然后打印路径

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void printPath(int l[], int n) {
    cout << "最优路径：" << endl;
    int line = l[n]; // 最后从哪条线出
    cout << "Line " << line << ", Station " << n - 1 << endl;

    for (int i = n - 1; i > 0; --i) {
        line = l[i];
        cout << "Line " << line << ", Station " << i - 1 << endl;
    }
}

矩阵链乘法

A的列数等于B的行数就可以$A \times B$

定义：

$A_i$表示矩阵i，一共n个

$p_{i-1} \times p_i$表示第i个矩阵的维度

目的：求出最小连乘运算量

方程：m[i,j]为$A_i$乘到$A_j$的最小运算量 $$ m[i,j] = \begin{cases} 0, &i=j, \ \min_{i \leq k < j} {m[i,k] + m[k+1,j]+p_{i-1}p_kp_j}, &i < j.

\end{cases} $$ 注：$p_{i-1}$即为$A_i$的行数，$p_j$即$A_j$的列数，

当你将两个矩阵 $ X: a \times b $ 和 $ Y: b \times c $ 相乘时，所需的标量乘法次数为： $$ a \cdot b \cdot c $$

所以，将上述两部分的结果矩阵相乘时，所需的乘法次数就是： $$ p_{i-1} \cdot p_k \cdot p_j $$ 代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

DpMatrix() {
    // 长度为 1
    for (int i = 0; i < n; i++)
        m[i][i] = 0;
    // 枚举长度
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len; i++) {
            int j = i + len - 1;
            for (int k = i; k < j; k++) {
                int tmp = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if (tmp < m[i][j]) {
                    m[i][j] = tmp;
                    s[i][j] = k; // 溯源存储
                }
            }
        }
    }
    return m and s;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void printOptimalParens(int s[][MAX], int i, int j) {
    if (i == j)
        cout << "A" << i;
    else {
        cout << "(";
        printOptimalParens(s, i, s[i][j]);
        printOptimalParens(s, s[i][j]+1, j);
        cout << ")";
    }
}

最长公共子序列

序列不需要连续

定义：字符串$X$长度为m和$Y$长度为n

目的：求出最长公共子序列

方程： $$ c[i,j] = \begin{cases} 0, &i=0 \space or\space j =0,\ c[i-1,j-1]+1,& i,j>0 \space and \space x_i == y_i,\ max{c[i-1,j],c[i,j-1]}, & i,j>0 \space and \space x_i \neq y_i. \end{cases} $$

代码：b[i][j]用来存是从哪里转移

表格i为行，j为列，填表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

LCS() {
    for (int i = 0; i < m; i++) c[i, 0] = 0;
    for (int i = 0; i < n; i++) c[0, i] = 0;
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
			if (X[i] == Y[j]) {
                c[i][j] = c[i-1]][j-1] + 1;
                b[i][j] = "左上";
            } else if (c[i-1][j] > c[i][j-1]) {
                c[i][j] = c[i-1][j];
                b[i][j] = "上";
            } else {
                c[i][j] = c[i][j-1];
                b[i][j] = "左";
            }
        }
    }
    return c[m-1][n-1];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

void print_LCS(int i, int j) {
    if (i == 0 || j == 0) return;

    if (b[i][j] == "左上") {
        print_LCS(i - 1, j - 1;
        cout << X[i - 1]; // 因为 X 是从 0 开始索引的
    }
    else if (b[i][j] == "上") {
        print_LCS(i - 1, j);
    }
    else { // "左"
        print_LCS(i, j - 1);
    }
}

答案不唯一

0/1背包

  • dp[i][j]：表示前 i 个物品，背包容量为 j 时，可以获得的最大价值。
  • dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i])：选择第 i 个物品，从 i-1 的状态转移过来（因为每个物品只能选一次）。

贪心

任务选择问题：

找最先结束的

证明：一个是最优子结构性质，另一个是贪心选择性质。

只证贪心选择：

问题描述：

  • 给定一组活动 S={a1,a2,…,an} ，每个活动 ai 有一个开始时间 si 和结束时间 fi 。
  • 活动之间互不重叠时是兼容的。目标是选出一个最大兼容活动集合。

贪心策略：

  • 每次选择最早结束 的活动 ak ，然后递归地处理与该活动兼容的剩余活动。

证明思路：

  • 假设 存在一个最优解 A 包含某个活动 aj ，而不是最早结束的活动 ak 。
  • 由于 ak 是最早结束的活动，那么它的结束时间 fk≤fj 。
  • 将 aj 替换为 ak 后，新的解 A′=(A−{aj})∪{ak} 仍然是一个有效解，并且大小与原解相同。
  • 因此，A′ 也是一个最优解，并且包含 ak 。
  • 这表明，选择最早结束的活动 不会影响最终得到一个最优解，即贪心选择是安全的。

完全背包

排序

霍夫曼

小根堆

图

会写代码即可

拓扑排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

const int N = 100010;
vector<int> adj[N];   // 邻接表
int indegree[N];      // 入度
vector<int> topo;     // 拓扑排序结果

int main() {
    int n, m; // n个点，m条边
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;  // u -> v
        adj[u].push_back(v);
        indegree[v]++;
    }

    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indegree[i] == 0)
            q.push(i);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int v : adj[u]) {
            if (--indegree[v] == 0)
                q.push(v);
        }
    }

    if (topo.size() == n) {
        for (int x : topo) cout << x << " ";
    } else {
        cout << "有环，无法拓扑排序";
    }
    return 0;
}

Prim

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

const int INF = 1e9;
int n, g[100][100]; // 邻接矩阵存图
int dis[100];       // 每个点到生成树的最小边权
bool vis[100];      // 是否已加入生成树

int prim() {
    fill(dis, dis + n, INF);
    dis[0] = 0;
    int res = 0;
    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int j = 0; j < n; ++j)
            if (!vis[j] && (u == -1 || dis[j] < dis[u]))
                u = j;
        vis[u] = true;
        res += dis[u];
        for (int v = 0; v < n; ++v)
            if (!vis[v])
                dis[v] = std::min(dis[v], g[u][v]);
    }
    return res;
}

Kruskal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

struct Edge {
    int u, v, w;
    bool operator<(const Edge& e) const {
        return w < e.w;
    }
};

int fa[100];
int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

int kruskal(int n, vector<Edge>& edges) {
    iota(fa, fa + n, 0);
    sort(edges.begin(), edges.end());
    int res = 0, cnt = 0;
    for (auto& e : edges) {
        int fu = find(e.u), fv = find(e.v);
        if (fu != fv) {
            fa[fu] = fv;
            res += e.w;
            if (++cnt == n - 1) break;
        }
    }
    return res;
}

Dijkstra

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

typedef pair<int, int> PII;
vector<PII> g[100]; // g[u] = {{v1, w1}, {v2, w2}, ...}
int dis[100];
bool vis[100];

void dijkstra(int s) {
    priority_queue<PII, vector<PII>, greater<>> pq;
    fill(dis, dis + 100, INF);
    dis[s] = 0;
    pq.emplace(0, s);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (auto [v, w] : g[u]) {
            if (dis[v] > d + w) {
                dis[v] = d + w;
                pq.emplace(dis[v], v);
            }
        }
    }
}

Floyd

1
2
3
4
5
6
7
8
9

const int INF = 1e9;
int n, d[100][100]; // d[i][j] 表示 i 到 j 的最短路径长度

void floyd() {
    for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
}

网络流

网络流的图由一个源点s，一个汇点t和一个有向图组成，s只有出边，t只有入边。

主要的目的是为了求最大流，相当于一个水管网络单位时间从s到t的最大流量。

每个边要么带权$w$表示其容量（capacity），要么用$u/v$来表示，u为流量(flow)，v为容量，u <= v。我们再称v-u为余量（residual）

流的性质：用$(u,v)$表示一条有向边，f是流量，c是容量

  1. 容量约束 $f(u,v) \leq c(u,v)$
  2. 反对称性 $f(u,v) = -f(v,u)$
  3. 流守恒，除了源点和汇点外，每个顶点的流入量等于流出量。 $\sum_{u \in V} f(u, v) = 0$

流量定义：从源点到该点的总流量。$ |f|= \sum_{u} f(s, u)$

先给出一个最简单的方法，但是不一定能求出最大值。

先画出一个余量图（初始和原图相同），对于余量图图，我们找到一个简单路径从s到t（无环），然后将容量均减去所有边中最小的容量，如果出现容量变成0了，那么就视作删去这条边，然后重复上述操作，直到没有s到t的简单路径存在。

然后用原图减去余量图就可以得到一个新图，以u/v的格式表示，就可以得到一个流。

这个方法的局限性在于如果选择的路径顺序不同，结果也可能不同，你无法保证你选择的路径顺序是最优的，而枚举所有的路径也是相当复杂的，所以我们需要下面的算法。

FordFulkerson 算法

该算法和上面的朴素算法基本一样。

  1. 画出余量图
  2. 进行下述循环直到找不到从s到t的简单路径
    • 找到s到t的简单路径
    • 路径所有边减去最小的容量
    • 给所有的路径加上减去容量的反向边（用另一种方式颜色/虚线表示便于区分），如果存在相同方向的可以进行合并

该方法弥补了之前方法无法反悔的缺陷，这使得它一定能找到最大流。

当然它也有缺陷，当它路径选择不当时每轮只能使其得到的流+1，所以它的最坏复杂度是O(f*m)，f是最大流，m是边数。

最大流最小割

这个是对找不到增广路径就是最大流情况的证明。

在流网络 G=(V,E) 中，设 s 为源点，t 为汇点，f 为 G 中的一个可行流。以下三个条件是等价的：

(1) f 是 G 中的最大流。

(2) 残量网络 Gf 中不存在增广路径。

(3) 存在某个割 (S,T)，使得 ∣f∣=c(S,T)（即流的值等于该割的容量）。

1->2:反证，存在增广路径就可以增加流，就不是最大流

3->1:根据最大流最小割定理，任意流的流量不超过任意割的容量。若 ∣f∣=c(S,T)，则 f 已达到理论最大值，故为最大流。

2->3：不存在到t的增广路径，我们让S为s能到的点，T为V-S，所以（S,T)划分是一个割，对于所有S到T的边都是饱和的，所以f(S,T)=c(S,T)，又由于f(S,T)=|f|所以可证。

最短路径增广SPA（Edmond-Karp ）

这个只是将Ford-Fulkerson的简单路径改成最短路径(使用BFS找到边数最小的，相当于权为1)，这样使得复杂度变成了O(n*m^2)。

备注一下：上面所有的简单路径也就是增广路径，路径上的最小容量也就是瓶颈容量。

二分图匹配

只掌握二分图转最大流求解。

  1. 构造流网络：
    • 添加一个源点 s 和一个汇点 t。
    • 从源点 s 向 U 中的每一个顶点 u 添加一条有向边，容量为 1。
    • 对于原二分图中的每一条边 (u,v)（其中 u∈U, v∈V），添加一条从 u 到 v 的有向边，容量为 1。
    • 从 V 中的每一个顶点 v 向汇点 t 添加一条有向边，容量为 1。
  2. 求解最大流：
    • 使用最大流算法计算从 s 到 t 的最大流。
    • 最大流的值即为二分图的最大匹配的大小。
    • 流网络中流量为 1 的 U 到 V 的边对应于匹配中的边。

P NP问题

P （Polynomial ）问题：能在多项式时间内解决的问题。 NP（Nondeterministic Polynomial ） 问题：解的正确性能在多项式时间内被验证。

判定问题：回答是否存在一个满足问题要求的解。

NPC (Completeness) 问题：

  1. 属于NP问题
  2. 所有NP问题可在多项式时间归约到它

NP-Hard问题：如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。因此NP困难问题“至少与NP完全问题一样难”。

归约：将问题 A 的实例 x 转换成问题 B 的实例 f(x)，使得：

  • 如果 x 是 A 的“是”实例，则 f(x) 也是 B 的“是”实例。
  • 如果 x 是 A 的“否”实例，则 f(x) 也是 B 的“否”实例。

在NP证明中我们要求归约函数 f 必须在多项式时间内计算完成。

回溯法

就是dfs

约束函数：判断当前部分解是否满足问题的约束条件。

​ 示例：在n皇后问题中，约束函数判断当前皇后是否和前面已放置的皇后冲突（同列/对角线等）。

限界函数：用于估计从当前部分解出发最优情况下也不可能超过当前已知最优解，从而剪枝。

装载问题

n个箱子，重量分别为$w_i$，最多装W，求出能装出最接近W的装法。

约束函数：$C(i) = cw(i-1) + w_i$

C(i)含义是：尝试加入第 i 个箱子后的总重量。

cw：当前累计重量（current weight）

限界函数：$B(i) = C(i) + r(i)$

r(i) 是从第 i+1 箱子开始，剩余还没尝试的所有箱子中可能加入的最大重量之和

剪枝的两种情况：

约束剪枝（可行性剪枝）：$C(i) > W$

限界剪枝（最优性剪枝）:$B(i) \leq bestw$

01背包

想要剪枝需要按照性价比先排序。

约束函数：$C(i) = cw(i-1) + w_i$

cw：当前累计重量（current weight）

限界函数：$B(i) = cv(i) + r(i)$

cv：当前累计价值（current value）

r(i)：剩余物品（从i+1）开始的最大总价值。

r(i)的计算：如果能装下去就装，装不下去就拆开装，因为最终的结果一定是小于等于这个贪心得到的值的，上界都不如目前的bestw就没必要继续搜索了。

约束剪枝（可行性剪枝）：$C(i) > W$

限界剪枝（最优性剪枝）:$B(i) \leq bestw$

分支限界

就是bfs剪枝+（优先）队列

01背包

约束函数：$C(i) = cw(i-1) + w_i$

cw：当前累计重量（current weight）

限界函数：$B(i) = cv(i) + r(i)$

cv：当前累计价值（current value）

r(i)：剩余物品（从i+1）开始的最大总价值。

解空间树的画法：

每个节点旁边是C(i)/B(i)，如果C(i)>W那么就似了，如果叶子节点的cv大于剩下的所有的B那么就结束了，每次从目前B(i)最高的值开始继续搜。

可满足性问题