贪心算法

贪心算法：在多阶段决策过程中，以当前状态为基础，根据特定贪心准则/优化测度进行局部最优决策，而不考虑各种可能的整体情况。自顶向下，以迭代做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题。

1. 分解：将原问题求解过程划分为连续的若干决策阶段；
2. 决策：在每一个决策阶段依据贪心策略进行贪心决策，得到局部最优解，并缩小待求解问题规模；
3. 合并：将各个决策阶段的局部最优解合并为原问题的全局可行解。

⭐贪心算法的设计模式：

S = {};
while (notSolution(S)) {
    x = Select(C);
    S = S + {x};
    C = C - Collection(x);
}
return S;

找零钱问题：

贪心要素	具体
候选集合 $\text {C}$	各种面值的货币
解集合 $\text {S}$	已付出的货币
可行解函数 $\text {Solution}$	已付出的货币面值等于应付金额
选择函数 $\text {Select}$	从候选集合中选择面值最大且不超过应付金额的货币

什么样的问题能用贪心算法求解？ $\Leftrightarrow$ 能用贪心算法求解的问题具有怎样的性质？

贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的决策得到。

（数学归纳法）证明过程：

1. 基础步：第 $\text {1}$ 次贪心决策可以导出整体最优解，或者说存在一个整体最优解包含第 $\text {1}$ 次贪心决策；
2. 归纳步：如果第 $\text {k}$ 次贪心决策可以导出整体最优解，那么第 $\text {k+1}$ 次贪心决策也能导出整体最优解。

（交换论证法）证明过程：

1. 基础步：给定任意一个整体最优解，把第 $\text {1}$ 次贪心决策后选择的对象替换最优解中的特定要素，证明替换后的新解也是整体最优解；
2. 交换步：证明上述交换过程可以循环进行。

活动安排问题

题目描述

假设某社团某一天要组织 $n$ 个活动 $E=\{1,2, \cdots, n\}$，其中每个活动都要求使用同一礼堂，而且在同一时间内只有一个活动能使用这个礼堂。每个活动 $i$ 都有一个要
求使用礼堂的起始时间 $s_i$ 和结束时间 $f_i$，且 $s_i < f_i$。如果选择了活动 $i$，则它在半开时间区间 $[s_i,f_i]$ 内占用资源。若区间 $[s_i,f_i]$ 与区间 $[s_j,f_j]$ 不相交，则称活动 $i$ 与活动 $j$ 是相容的。现在给定 $n$ 个活动的开始时间和结束时间，请设计一个活动安排方案，使得安排的相容活动数目最多。

输入数据

多组测试数据。每组测试数据包含三行：

• 第一行输入活动数目 $n(n<1000)$；
• 第二行输入 $n$ 个活动的开始时间；
• 第三行输入 $n$ 个活动的结束时间。

这里规定所有的时间取值范围为 $1$ 到 $1000$ 间的整数。

输出数据

最多安排的相容活动数目，每组测试数据输出一行。

样例输入

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

样例输出

4

问题分析

策略一：选择具有最早开始时间，而且不与已安排的活动冲突的活动。

策略二：选择具有最短使用时间，而且不与已安排的活动冲突的活动。

策略三：选择具有最早结束时间，而且不与已安排的活动冲突的活动。

综合策略一和二 $\Rightarrow$ 选择开始时间最早且最短使用时间的活动，又活动结束时间等于开始时间加上使用时间，组合策略就是策略三。

算法实现与分析

设计思路：

1. 所有活动按照结束时间进行升序排序

$\text {E}[1] . f \leqslant \text {E}[2] . f \leqslant \cdots \leqslant \text {E}[n] . f$

2. 选择 $\text {E}[1]$，记录 $\text {E}[1]=true$

3. 依次扫描 $\text {E}[i]$

if startTime(E[i]) > lastSelectedEnd then
    A[i] = true
    lastSelectedEnd = endTime(E[i])
else
    A[i] = false
end for

🏠活动安排的贪心算法：

#include <iostream>
#include <cstdio>
#define MaxEvent 1000

int s[MaxEvent];
int f[MaxEvent];
int greedyEvebntSchedule(int, int *, int *);

int greedyEvebntSchedule(int n, int *timeStart, int *timeFinish)
{
    int selected, ans = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j + 1 < n; j++)
            if (timeFinish[j] > timeFinish[j + 1])
            {
                std::swap(timeFinish[j], timeFinish[j + 1]);
                std::swap(timeStart[j], timeStart[j + 1]);
            }
    }
    selected = 0;
    ans = 1;
    for (int i = 1; i < n; i++)
        if (timeStart[i] >= timeFinish[selected])
        {
            selected = i;
            ans++;
        }
    return ans;
}

int main()
{
    int n, ans;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &s[i]);
        for (int i = 0; i < n; i++)
            scanf("%d", &f[i]);
        ans = greedyEvebntSchedule(n, s, f);
        printf("%d\n", ans);
    }
    return 0;
}

👉时间复杂度：$O\left(n^2\right)$

对于样例：

$i$	1	2	3	4	5	6	7	8	9	10	11
$E[i],s$	1	3	0	5	3	5	6	8	8	2	12
$E[i],f$	4	5	6	7	8	9	10	11	12	13	14

1. 活动 1：开始时间 1，结束时间 4。由于这是第一个活动，我们选择它。目前选中的活动：{1}。
2. 活动 2：开始时间 3，结束时间 5。它的开始时间早于活动 1 的结束时间，因此不能选择它。目前选中的活动：{1}。
3. 活动 3：开始时间 0，结束时间 6。它的结束时间晚于活动 1 的结束时间，但开始时间早于活动 1 的结束时间，因此不能选择它。目前选中的活动：{1}。
4. 活动 4：开始时间 5，结束时间 7。它的开始时间晚于活动 1 的结束时间，因此我们选择它。目前选中的活动：{1, 4}。
5. 活动 5：开始时间 3，结束时间 8。它的开始时间早于活动 4 的结束时间，因此不能选择它。目前选中的活动：{1, 4}。
6. 活动 6：开始时间 5，结束时间 9。它的开始时间早于活动 4 的结束时间，因此不能选择它。目前选中的活动：{1, 4}。
7. 活动 7：开始时间 6，结束时间 10。它的开始时间晚于活动 4 的结束时间，因此我们选择它。目前选中的活动：{1, 4, 7}。
8. 活动 8：开始时间 8，结束时间 11。它的开始时间早于活动 7 的结束时间，因此不能选择它。目前选中的活动：{1, 4, 7}。
9. 活动 9：开始时间 8，结束时间 12。它的开始时间晚于活动 7 的结束时间，因此我们选择它。目前选中的活动：{1, 4, 7, 9}。
10. 活动 10：开始时间 2，结束时间 13。它的开始时间早于活动 9 的结束时间，因此不能选择它。目前选中的活动：{1, 4, 7, 9}。
11. 活动 11：开始时间 12，结束时间 14。它的开始时间晚于活动 9 的结束时间，因此我们选择它。目前选中的活动：{1, 4, 7, 9, 11}。

最终选中的活动集合是 {1, 4, 7, 9, 11}。

命题：算法 $\text {GreedySelector}$ 执行第 $\text {k}$ 步，选择 $\text {k}$ 项活动 $i_1=1, i_2, \cdots, i_k$，那么存在一个最优解包含 $i_1=1, i_2, \cdots, i_k$。

证明：

集合 $\text {S}$ 按照活动结束时间排序：$\{1,2, \cdots, n\}$

最优解 $\text {A}$ ：$\left\{j_1, j_2, \cdots, j_m\right\}$

• 基础步：$k=1$
  • 如果 $j_1=1$，$\text {A}$ 包含活动 $1$
  • 如果 $j_1 \neq 1$，用活动 $1$ 替换 $j_1$，得到 $\text {A}^{\prime}$，即

$\text {A}^{\prime}=\left\{\text {A}^{\prime}-\left\{j_1\right\}\right\} \cup\{1\}$

因为活动 $1$ 结束时间比活动 $j_1$ 结束时间早 $\Rightarrow$ $\text {A}^{\prime}$ 与 $\text {A}$ 相容

那么 $\text {A}^{\prime}$ 也是最优解。

• 归纳步：假设对于正整数 $\text {k}$ 命题正确

存在一个最优解，

$\text {A}=\left\{i_1=1, i_2, \cdots, i_k\right\} \cup \text {B}$

又 $\text {S}^{\prime}=\left\{j \mid \text {E}[j] . s \geqslant \text {E}\left[i_k\right] . f, j \in \text {S}\right\}$

$\text {B}$ 是 $\text {S}^{\prime}$ 的一个最优解，否则至少存在 $\text {B}^{\prime}$ 有 $\left|\text {B}^{\prime}\right|>|\text {B}|$

$\text {A}^{\prime}=\left\{i_1=1, i_2, \cdots, i_k\right\} \cup \text {B}^{\prime}$

与 $\text {A}$ 是最优解矛盾。

假设 $\text {B}^{\prime}$ 是 $\text {S}^{\prime}$ 的一个最优解，根据基础步

$\text {B}^{\prime \prime}=\left\{i_{k+1}, \cdots\right\}$

（$i_{k+1}$ 是 $\text {S}^{\prime}$ 结束时间最早的活动）

又 $\text {B}$ 和 $\text {B}^{\prime}$ 都是是 $\text {S}^{\prime}$ 的最优解，故 $\left|\text {B}^{\prime \prime}\right|=|\text {B}|$

$\text {A}^{\prime}=\left\{i_1=1, i_2, \cdots, i_k\right\} \cup \text {B}^{\prime \prime}=\left\{i_1=1, i_2, \cdots, i_k, i_{k+1}\right\} \cup\left\{\text {B}^{\prime \prime}-\left\{i_{k+1}\right\}\right\}$

且 $\left|\text {A}^{\prime}\right|=|\text {A}|$，$\text {A}^{\prime}$ 包含了算法 $\text {GreedySelector}$ 的前 $k+1$ 步选择的活动。

小数背包问题

题目描述

给定 $n$ 种物品和一个背包。物品 $i$ 的重量是 $W_i$，其价值为$V_i$，背包的容量为 $C$，应如何选择装入背包的物品使得装入背包中物品的总价值最大？这里，在选择物品 $i$ 装入
背包时，可以选择物品 $i$ 的一部分，而不一定要全部装入背包。

输入数据

多组测试数据。每组测试包括三行：

• 第一行输入物品的总数 $n(n<1000)$ 和背包的容量 $\text {C}(\text {C}<1000)$。
• 第二行输入 $n$ 个整数，表示物品的重量。
• 第三行输入物品的价值。

输出数据

装入背包的总价值，每组测试数据输出一行。

样例输入

3 50
10 20 30
60 100 120

样例输出

20

问题分析

小数背包模型：

$\max \sum_{i=1}^n v_i x_i$

$\text { st. }\left\{\begin{array}{l} \sum_{i=1}^n w_i x_i \leqslant C \\ 0 \leqslant x_i \leqslant 1,1 \leqslant i \leqslant n \end{array}\right.$

策略一：在不超出当前背包的剩余容量前提下，选择具有价值最大的物品。

策略二：在不超出当前背包的剩余容量前提下，选择具有重量最轻的物品。

策略三：在不超出当前背包的剩余容量前提下，选择具有价值率（价值除以重量）最大的物品。

算法实现与分析

设计思路：

1. 所有物品按照价值率进行降序排序

$\text {itme}[1] . v \geqslant \text {itme}[2] . v \geqslant \cdots \geqslant \text {itme}[n] . v$

2. 选择 $\text {itme}[1]$，并记录 $\text {itme}[1] . w$。

3. 依次扫描 $\text {itme}[i]$，在没有超出背包容量的条件下，尽可能多地装入当前价值率最
   高的物品，并记录 $\text {itme}[i] . w$。

🏠小数背包的贪心算法：

#include <iostream>
#include <cstdio>
#include <algorithm>
#define MaxItem 1000

struct item
{
    int weight;
    int value;
    bool operator<(const item &another) const
    {
        return value / (1.0 * weight) > another.value / (1.0 * another.weight);
    }
};

item items[MaxItem];
double greedyKnapsack(int, int, item *);

double greedyKnapsack(int n, int capacity, item *items)
{
    double ans = 0;
    std::sort(items, items + n);
    for (int i = 0; i < n; i++)
        if (capacity >= items[i].weight)
        {
            ans += items[i].value;
            capacity -= items[i].weight;
        }
        else
        {
            ans += capacity * (items[i].value * 1.0) / items[i].weight;
            break;
        }
    return ans;
}

int main()
{
    int n, capacity;
    double ans;
    while (scanf("%d %d", &n, &capacity) != EOF)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &(items[i].weight));
        for (int i = 0; i < n; i++)
            scanf("%d", &(items[i].value));
        ans = greedyKnapsack(n, capacity, items);
        printf("%.2f\n", ans);
    }
    return 0;
}

👉时间复杂度：$O(n \log n)$

最优前缀码

题目描述

二元前缀码：在计算机中需要用 $0,1$ 字符串作为代码来表示信息，为了正确解码必须要求任何字符的代码不能作为其他字符代码的前缀。

$C=\left\{x_1, x_2, \cdots, x_n\right\}$：$n$ 个字符集合。

$f(x_i),(i=1,2,\cdots,n)$：字符 $x_i$ 频次。

$d(x_i),(i=1,2,\cdots,n)$：字符 $x_i$ 码长。

平均码长：

$B(T)=\frac{\sum_{i=1}^n f\left(x_i\right) d\left(x_i\right)}{\sum_{i=1}^n f\left(x_i\right)}$

最优前缀码：平均码长最小的前缀码方案。

定长编码：字符集的每个字符用相同码长的代码表示。

变长编码：字符集的每个字符用不同码长的代码表示。

输入数据

多组测试数据。每组测试数据包含两行：

• 第一行输入字符集中字符的个数 $n(n<1000)$;
• 第二行输入每个字符出现的频次 $<1000$。

输出数据

最优前缀码的平均码长，保留 $4$ 位小数。每组测试数据输出一行。

样例输入

6
45 13 12 16 9 5

样例输出

2.2400

问题分析

哈夫曼编码：给频率高的字符编较短的代码，频率低的字符编较长的代码，把编码映射成二叉树。

贪心策略：把频率高的字符分配给靠近根结点（较浅）的叶子结点，把频率低的字符放置在远离根结点（较深）的叶子结点。

算法实现与分析

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#define MaxChar 1000

int freq[MaxChar];
double haffmanCoding(int, int *);

struct cmp
{
    bool operator()(const int &x, const int &y)
    {
        return x > y;
    }
};

double haffmanCoding(int n, int *freq)
{
    int total = 0, sumFreq = 0;
    std::priority_queue<int, std::vector<int>, cmp> heap;
    for (int i = 0; i < n; i++)
    {
        total += freq[i];
        heap.push(freq[i]);
    }
    while (heap.size() > 1)
    {
        int jointFreq = 0;
        for (int i = 0; i < 2; i++)
        {
            jointFreq += heap.top();
            heap.pop();
        }
        sumFreq += jointFreq;
        heap.push(jointFreq);
    }
    double avgFreq = sumFreq / (1.0 * total);
    return avgFreq;
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
            scanf("%d", &freq[i]);
        double codeLength = haffmanCoding(n, freq);
        printf("%.4f\n", codeLength);
    }
    return 0;
}

👉时间复杂度：$O(n \log n)$

基础步：设字符集 $C$ 中每个字符 $c$ 的频率为 $f(c)$，$x$ 和 $y$ 是 $C$ 中频率最低的两个字符，则存在 $C$ 的最优前缀码使得 $x$ 和 $y$ 的代码长度相同（最后一位编码不同），且它们的代码长度是所有字符中最长的。

证明：

$a$ 和 $b$ 是最深叶子节点且互为兄弟，二叉树 $T$（最优前缀码），适当修改

$\Rightarrow$ $x$ 和 $y$ 是最深叶子节点且互为兄弟，二叉树 $T^{\prime \prime}$

又 $x$ 和 $y$ 是 $C$ 中频率最低的两个字符

$f(x) \leqslant f(y) \leqslant f(a) \leqslant f(b)$

交换叶子节点 $b$ 和 $x$，交换叶子节点 $a$ 和 $y$，$T \rightarrow T^{\prime} \rightarrow T^{\prime \prime}$

$T$ 和 $T^{\prime}$ 前缀码平均码长之差：

$\begin{aligned} B(T)-B\left(T^{\prime}\right) & =\sum_{c \in C} f(c) d_T(c)-\sum_{c \in C} f(c) d_{T^{\prime}}(c) \\ & =f(x) d_T(x)+f(b) d_T(b)-f(x) d_{T^{\prime}}(x)-f(b) d_{T^{\prime}}(b) \\ & =f(x) d_T(x)+f(b) d_T(b)-f(x) d_T(b)-f(b) d_T(x) \\ & =(f(b)-f(x))\left(d_T(b)-d_T(x)\right) \geqslant 0 \end{aligned}$

其中 $d_{T^{\prime}}(x)=d_T(b), d_{T^{\prime}}(b)=d_{T\}}(x)$，省略分母 $\sum_{i=1}^n f\left(x_i\right)$

$T^{\prime}$ 和 $T^{\prime \prime}$ 前缀码平均码长之差：

$\begin{aligned} B(T^{\prime})-B\left(T^{\prime \prime}\right) & =\sum_{c \in C} f(c) d_{T^{\prime}}(c)-\sum_{c \in C} f(c) d_{T^{\prime \prime}}(c) \\ & =f(y) d_{T^{\prime}}(y)+f(a) d_{T^{\prime}}(a)-f(y) d_{T^{\prime \prime}}(y)-f(a) d_{T^{\prime \prime}}(a) \\ & =f(y) d_{T^{\prime}}(y)+f(a) d_{T^{\prime}}(a)-f(y) d_{T^{\prime}}(a)-f(a) d_{T^{\prime}}(y) \\ & =(f(a)-f(y))\left(d_{T^{\prime}}(a)-d_{T^{\prime}}(y)\right) \geqslant 0 \end{aligned}$

其中 $d_{T^{\prime \prime}}(y)=d_{T^{\prime}}(a), d_{T^{\prime \prime}}(a)=d_{T^{\prime}}(y)$，省略分母 $\sum_{i=1}^n f\left(x_i\right)$

综合前面两步：

$B(T) \geqslant B\left(T^{\prime}\right) \geqslant B\left(T^{\prime \prime}\right)$

又二叉树 $T$ 是最优前缀码

$B(T) \leqslant B\left(T^{\prime \prime}\right)$

因此

$B(T)=B\left(T^{\prime \prime}\right)$

二叉树 $T^{\prime \prime}$ 也是最优前缀码， $x$ 和 $y$ 的代码长度相同（最后一位编码不同），且它们的代码长度是所有字符中最长的。

交换步：二叉树 $T$ 是字符集 $C$ 的一个最优前缀码，

单源最短路径

题目描述

给定带权有向图 $G(V,E)$ ，其中每条边的权都是非负实数。另外，还给定 $V$ 中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路径长度，假设从源可以到达任何一个顶点。这里路径的长度是指路径上各边权之和。这个问题通常称为单源最短路径
问题。

输入数据

多组测试数据。

• 第一行输入图 $G$ 中顶点的个数 $n$（$n<1000$）;
• 后续 $n$ 行 $n$ 列输入图 $G$ 的权值矩阵，其中第 $i$ 行第 $j$ 列的值表示从第 $i$ 个顶点到第 $j$ 个顶点的有向的权值，如果为 $-1$ 则表示从第 $i$ 个顶点到第 $j$个顶点没有边相连。默认第一个顶点为源。

输出数据

从源到所有其他各顶点的最短路径长度之和。每组测试数据输出一行。

样例输入

5
-1 10 -1 30 100
-1 -1 50 -1 -1
-1 -1 -1 -1 10
-1 -1 20 -1 60
-1 -1 -1 -1 -1

样例输出

150

问题分析

算法实现与分析

• $linkMatrix[u][x]$

• $lowLR[x]$：源到顶点 $x$ 的最短受限路径长度（若 $x$ 属于最短路径树，到顶点 $x$ 的最短路径长度）。

• $preV[x]=u$：源到顶点 $x$ 的最短路径，$u$ 是 $x$ 的前驱顶点。

1. $S=\{u\}$，$v \in V-S=\{ \cdots \}$：

$\begin{aligned} & lowLR[v] = linkMatrix[u][v],preV[v]=u \\ & st. (u, v) \in E\end{aligned}$

5. 在 $V-S$ 中选择 $LowLR[]$ 最小顶点 $t$，$LowLR[t]=\min \{lowLR[x] \mid x \in(V-S)\}$；
6. 将顶点 $t$ 加入 $S$，更新 $V-S$，更新 $LowLR[]$：

$\begin{aligned} & lowLR[x]=lowLR[t]+linkMatrix[t][x],preV[x]=t \\ & st. lowLR[x]>lowLR[t]+linkMatrix[t][x]\end{aligned}$

4. 循环 $2$，$3$，直到 $V-S$ 为空。

求解步骤如下

（2）$t=A$

$S$	$V-S$
$A$	$B,C,D,E,F,G,H,I$

$A$	$LowLR[]$	$preV[]$
$B$	$9$	$A$	$A \rightarrow B$
$C$	$2$	$A$	$A \rightarrow C$
$D$	$6$	$A$	$A \rightarrow D$
$E$	$+\infty$	$A$	$*$
$F$	$+\infty$	$A$	$*$
$G$	$+\infty$	$A$	$*$
$H$	$+\infty$	$A$	$*$
$I$	$+\infty$	$A$	$*$

（3）$t=C$

$S$	$V-S$
$A,C$	$B,D,E,F,G,H,I$

• $D$：$lowLR[D]=6$

$lowLR[C]+linkMatrix[C][D]=2+3=5$，$lowLR[D]=5$，$preV[D]=C$

• $F$：$lowLR[F]=+\infty$

$lowLR[C]+linkMatrix[C][F]=2+1=3$，$lowLR[F]=3$，$preV[F]=C$

$A$	$LowLR[]$	$preV[]$
$B$	$9$	$A$	$A \rightarrow B$
$C$	$2$	$A$	$A \rightarrow C$
$D$	$5$	$C$	$A \rightarrow C \rightarrow D$
$E$	$+\infty$	$*$	$*$
$F$	$3$	$C$	$A \rightarrow C \rightarrow F$
$G$	$+\infty$	$*$	$*$
$H$	$+\infty$	$*$	$*$
$I$	$+\infty$	$*$	$*$

（4）$t=F$

S	V-S
$A,C,F$	$B,D,E,G,H,I$

• $D$：$lowLR[D]=5$

$lowLR[F]+linkMatrix[F][D]=3+1=4$，$lowLR[D]=4$，$preV[D]=F$

• $I$：$lowLR[I]=+\infty$

$lowLR[F]+linkMatrix[F][I]=3+6=9$，$lowLR[I]=9$，$preV[I]=F$

$A$	$LowLR[]$	$preV[]$
$B$	$9$	$A$	$A \rightarrow B$
$C$	$2$	$A$	$A \rightarrow C$
$D$	$4$	$F$	$A \rightarrow C \rightarrow F \rightarrow D$
$E$	$+\infty$	$*$	$*$
$F$	$3$	$C$	$A \rightarrow C \rightarrow F$
$G$	$+\infty$	$*$	$*$
$H$	$+\infty$	$*$	$*$
$I$	$9$	$F$	$A \rightarrow C \rightarrow F \rightarrow I$

（5）$t=D$

S	V-S
$A,C,D,F$	$B,E,G,H,I$

• $B$：$lowLR[B]=9$

$lowLR[D]+linkMatrix[D][B]=4+2=6$，$lowLR[B]=6$，$preV[B]=D$

• $E$：$lowLR[E]=+\infty$

$lowLR[D]+linkMatrix[D][E]=4+7=11$，$lowLR[E]=11$，$preV[E]=D$

• $G$：$lowLR[G]=+\infty$

$lowLR[D]+linkMatrix[D][G]=4+9=13$，$lowLR[G]=13$，$preV[G]=D$

$A$	$LowLR[]$	$preV[]$
$B$	$6$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow B$
$C$	$2$	$A$	$A \rightarrow C$
$D$	$4$	$F$	$A \rightarrow C \rightarrow F \rightarrow D$
$E$	$11$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow E$
$F$	$3$	$C$	$A \rightarrow C \rightarrow F$
$G$	$13$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow G$
$H$	$+\infty$	$*$	$*$
$I$	$9$	$F$	$A \rightarrow C \rightarrow F \rightarrow I$

（6）$t=B$

S	V-S
$A,B,C,D,F$	$E,G,H,I$

• $E$：$lowLR[E]=11$

$lowLR[B]+linkMatrix[B][E]=6+4=10$，$lowLR[D]=10$，$preV[E]=B$

$A$	$LowLR[]$	$preV[]$
$B$	$6$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow B$
$C$	$2$	$A$	$A \rightarrow C$
$D$	$4$	$F$	$A \rightarrow C \rightarrow F \rightarrow D$
$E$	$11$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow E$
$F$	$3$	$C$	$A \rightarrow C \rightarrow F$
$G$	$13$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow G$
$H$	$+\infty$	$*$	$*$
$I$	$9$	$F$	$A \rightarrow C \rightarrow F \rightarrow I$

（7）$t=I$

S	V-S
$A,B,C,D,F,I$	$E,G,H$

• $H$：$lowLR[H]=+\infty$

$lowLR[I]+linkMatrix[I][H]=9+5=14$，$lowLR[H]=14$，$preV[H]=I$

$A$	$LowLR[]$	$preV[]$
$B$	$6$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow B$
$C$	$2$	$A$	$A \rightarrow C$
$D$	$4$	$F$	$A \rightarrow C \rightarrow F \rightarrow D$
$E$	$11$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow E$
$F$	$3$	$C$	$A \rightarrow C \rightarrow F$
$G$	$13$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow G$
$H$	$14$	$I$	$A \rightarrow C \rightarrow F \rightarrow I \rightarrow H$
$I$	$9$	$F$	$A \rightarrow C \rightarrow F \rightarrow I$

（8）$t=E$

S	V-S
$A,B,C,D,E,F,I$	$G,H$

• $G$：$lowLR[G]=13$

$lowLR[E]+linkMatrix[E][G]=11+1=12$，$lowLR[G]=12$，$preV[G]=E$

• $H$：$lowLR[H]=14$

$lowLR[E]+linkMatrix[E][H]=11+5=16$，不修改

$A$	$LowLR[]$	$preV[]$
$B$	$6$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow B$
$C$	$2$	$A$	$A \rightarrow C$
$D$	$4$	$F$	$A \rightarrow C \rightarrow F \rightarrow D$
$E$	$11$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow E$
$F$	$3$	$C$	$A \rightarrow C \rightarrow F$
$G$	$13$	$E$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow E \rightarrow G$
$H$	$14$	$I$	$A \rightarrow C \rightarrow F \rightarrow I \rightarrow H$
$I$	$9$	$F$	$A \rightarrow C \rightarrow F \rightarrow I$

（9）$t=G$

S	V-S
$A,B,C,D,E,F,G,I$	$H$

• $H$：$lowLR[H]=14$

$lowLR[G]+linkMatrix[G][H]=13+5=18$

$A$	$LowLR[]$	$preV[]$
$B$	$6$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow B$
$C$	$2$	$A$	$A \rightarrow C$
$D$	$4$	$F$	$A \rightarrow C \rightarrow F \rightarrow D$
$E$	$11$	$D$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow E$
$F$	$3$	$C$	$A \rightarrow C \rightarrow F$
$G$	$13$	$E$	$A \rightarrow C \rightarrow F \rightarrow D \rightarrow E \rightarrow G$
$H$	$14$	$I$	$A \rightarrow C \rightarrow F \rightarrow I \rightarrow H$
$I$	$9$	$F$	$A \rightarrow C \rightarrow F \rightarrow I$

#include <cstdio>
#include <cstring>
#define INF 0x03F3F3F3F
#define MaxV 100

int linkMatrix[MaxV][MaxV];
int preV[MaxV];
int LowLR[MaxV];
int visited[MaxV];
void Dijkstra(int, int);

void Dijkstra(int n, int u)
{
    memset(visited, 0, sizeof(visited));
    LowLR[u] = 0;
    preV[u] = -1;
    visited[u] = 1;
    for (int i = 1; i < n; i++)
    {
        LowLR[i] = linkMatrix[u][i];
        preV[i] = u;
    }
    int selectV = u;
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int newCost = LowLR[selectV] + linkMatrix[selectV][j];
            if (visited[j] == 0 && newCost < LowLR[j])
            {
                LowLR[j] = newCost;
                preV[j] = selectV;
            }
        }
        int min = INF;
        for (int j = 0; j < n; j++)
            if (visited[j] == 0 && LowLR[j] < min)
            {
                min = LowLR[j];
                selectV = j;
            }
        visited[selectV] = 1;
    }
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &linkMatrix[i][j]);
                if (linkMatrix[i][j] == -1)
                    linkMatrix[i][j] = INF;
            }
        Dijkstra(n, 0);
        int totalCost = 0;
        for (int i = 0; i < n; i++)
            totalCost += LowLR[i];
        printf("%d\n", totalCost);
    }
    return 0;
}

最小生成树

题目描述

设 $G=(V,E)$ 是无向连通带权图。$E$ 中每条边 $(v,w)$ 的权为 $C(v,w)$。如果 $G$ 的子 $G^{\prime}$ 是一棵包含 $G$ 的所有顶点的树，则称 $G^{\prime}$ 为 $G$ 的生成树。生成树上各边权的总和称为该生成树的耗费。在G 的所有生成树中，耗费最小的生成树称为 $G$ 的最小生成树。请设计算法计算 $G$ 的最小生成树的权重总和。

输入数据

多组测试数据。每组测试数据

• 第一行输入图 $G$ 中顶点的个数 $n(n<1000)$；
• 后续 $n$ 行输入图 $G$ 的权值矩阵 $C$。第 $i$ 行第 $j$ 列 $j \leq i$ 的值表示边 $(i,j)$ 的权值，如果为 $-1$ 则表示从第 $i$ 个顶点到第 $j$ 个顶点没有边相连。

输出数据

最小生成树权重之和，每组测试数据输出一行。

样例输入

6
0
6 0
1 5 0
5 -1 5 0
-1 3 6 -1 0
-1 -1 4 2 6 0

样例输出

15

问题分析

最小生成树（$Minimum \ Spanning \ Trees$，$MST$）：设 $G=(V,E)$ 是连通带权图，$U$ 是 $V$ 的真子集，如果 $(u,v) \in E$，其中 $u \in U,v \in (V-U)$，且在所有这样的边中，$(u,v)$ 的权 $C(u,v)$ 最小，那么一定存在 $G$ 的一颗最小生成树，包含 $(u,v)$。

证明：

假设 $G$ 的任何一颗最小生成树 $T$ 都不含边 $(u,v)$。

将边 $(u,v)$ 添加到 $G$ 的一颗最小生成树 $T$ 上，将产生含有边 $(u,v)$ 的圈，并且在这圈中有不同于边 $(u,v)$ 的边 $(u^{\prime},v^{\prime})$ ，有 $u^{\prime} \in U$，$v^{\prime} \in V-U$。

将 $(u^{\prime},v^{\prime})$ 删除，得到另一个生成树 $T^{\prime}$，又 $C(u, v) \leqslant C\left(u^{\prime}, v^{\prime}\right)$

因此 $T^{\prime}$ 权重总和小于 $T$ 权重总和，$T^{\prime}$ 是 $G$ 的一颗含边 $(u,v)$ 的最小生成树，与假设矛盾。

算法实现与分析

$G=(V,E)$：无向带权图，$V=\{1,2, \cdots, n\}$。

$MST=(U, TE)$：最小生成树，$U \subseteq V$，$TE \subseteq E$。

Prim

1. 将任意顶点 $u_0$ 加入 $U$，$U=\left\{u_0\right\}$，$TE=\{\}$
2. 选取满足条件的 $i \in U$，$j \in V-U$，且边 $(i,j)$ 是连接 $U$ 和 $V-U$ 的所有边的最短边，顶点 $j$ 加入 $U$，边$(i,j)$ 加入 $TE$ 。
3. 循环执行 $2$，直到 $U=V$。

得到的 $U$ 和 $TE$ 构成 $G$ 的一颗最小生成树。

• $linkMatrix[u][x]$

• $LowCost[j]$：满足 $i \in U$，$j \in V-U$ 的最短边 $(i,j)$ 的权值。

• $closest[j]$：满足 $i \in U$，$j \in V-U$ 的最短边 $(i,j)$ 的顶点 $i$。

$\text{linkMatrix}[i][j] = \begin{cases} E(i, j), & \langle i, j \rangle \in E \\ \infty \end{cases}$

2. $U=\{u\}$，$v \in V-U=\{\cdots\}$：

$\begin{aligned} & LowCost[v]=linkMatrix[u][v],closest[v]=u \\ & st. (u, v) \in E\end{aligned}$

5. 在 $V-U$ 中选择 $LowCost[]$ 最小顶点 $t$，$LowCost[t]=\min \{LowCost[x] \mid x \in(V-U)\}$；

6. 将顶点 $t$ 加入 $U$，更新 $V-U$，更新 $LowCost[]$ 和 $closest[]$：

$\begin{aligned} & LowCost[x]=linkMatrix[t][x],closest[t]=x \\ & st. LowCost[x]>linkMatrix[t][x]\end{aligned}$

循环 $3$，$4$，直到 $V-U$ 为空。

$\text {epoch}$	$U$	$U-V$	$LowCost[]$	$visted[]$	$t$
$a$	$\{1\}$	$\{2,3,4,5,6\}$	$[0,6,1,5,\infty,\infty]$	$[1,0,0,0,0,0]$	$3$
$b$	$\{1,3\}$	$\{2,4,5,6\}$	$[0,5,1,5,6,4]$	$[1,0,1,0,0,0]$	$6$
$c$	$\{1,3,6\}$	$\{2,4,5\}$	$[0,5,1,2,6,4]$	$[1,0,1,0,0,1]$	$4$
$d$	$\{1,3,4,6\}$	$\{2,5\}$	$[0,5,1,2,6,4]$	$[1,0,1,1,0,1]$	$2$
$e$	$\{1,2,3,4,6\}$	$\{5\}$	$[0,5,1,2,3,4]$	$[1,1,1,1,0,1]$	$5$
$f$	$\{1,2,3,4,5,6\}$	$\{\}$	$[0,5,1,2,3,4]$	$[1,1,1,1,1,1]$

#include <cstdio>
#include <cstring>
#define INF 0x03F3F3F3F
#define MaxV 100

int linkMatrix[MaxV][MaxV];
int closest[MaxV];
int LowCost[MaxV];
int visited[MaxV];
int Prim(int);

int Prim(int n)
{
    memset(visited, 0, sizeof(visited));
    LowCost[0] = 0;
    closest[0] = -1;
    visited[0] = 1;
    for (int i = 1; i < n; i++)
    {
        LowCost[i] = linkMatrix[0][i];
        closest[i] = 0;
    }
    int costMST = 0;
    for (int i = 1; i < n; i++)
    {
        int min = INF;
        int selectV = 0;
        for (int k = 1; k < n; k++)
            if (!visited[k] && LowCost[k] < min)
            {
                min = LowCost[k];
                selectV = k;
            }
        costMST += min;
        visited[selectV] = 1;
        for (int k = 1; k < n; k++)
            if (!visited[k] && linkMatrix[selectV][k] < LowCost[k])
            {
                LowCost[k] = linkMatrix[selectV][k];
                closest[k] = selectV;
            }
    }
    return costMST;
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                linkMatrix[i][j] = INF;
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= i; j++)
            {
                scanf("%d", &linkMatrix[i][j]);
                if (linkMatrix[i][j] == -1)
                    linkMatrix[i][j] = INF;
                linkMatrix[j][i] = linkMatrix[i][j];
            }
        printf("%d\n", Prim(n));
    }
    return 0;
}

👉时间复杂度：$O(n^2)$

Kruskal

1. 将权值最小的边 $(i,j)$ 加入 $TE$，$U=\left\{i,j\right\}$，$TE=\{(i,j)\}$
2. 循环执行 $1$（避免出现环路），直到 $U=V$。

得到的 $U$ 和 $TE$ 构成 $G$ 的一颗最小生成树。

使用并查集。

#include <cstdio>
#include <cstdlib>
#define MaxV 100
#define MaxE 10000

struct edge
{
    int u, v;
    int w;
};

struct node
{
    int father;
    int height;
};

node juSet[MaxV];
edge edgeSet[MaxE];
int cmp(const void *, const void *);
int Find_Set(int);
void Union(int, int);
int Kruskal(int, int);

int cmp(const void *a, const void *b)
{
    if ((*(struct edge *)a).w == (*(struct edge *)b).w)
    {
        return (*(struct edge *)a).u - (*(struct edge *)b).u;
    }
    return (*(struct edge *)a).w - (*(struct edge *)b).w;
}

int Find_Set(int x)
{
    while (x != juSet[x].father)
        x = juSet[x].father;
    return x;
}

void Union(int i, int j)
{
    if (i == j)
        return;
    if (juSet[i].height > juSet[j].height)
        juSet[j].father = i;
    else
    {
        if (juSet[i].height == juSet[j].height)
            juSet[j].height++;
        juSet[i].father = j;
    }
}

int Kruskal(int numV, int numE)
{
    qsort(edgeSet, numE, sizeof(struct edge), cmp);
    int costMST = 0;
    for (int k = 0, cntE = 0; k < numE; k++)
    {
        int fatherU = Find_Set(edgeSet[k].u);
        int fatherV = Find_Set(edgeSet[k].v);
        if (fatherU != fatherV)
        {
            Union(fatherU, fatherV);
            costMST += edgeSet[k].w;
            cntE++;
        }
        if (cntE == numV - 1)
            return costMST;
    }
    return costMST;
}

int main()
{
    int numV, numE = 0;
    while (scanf("%d", &numV) != EOF)
    {
        for (int i = 0; i < numV; i++)
        {
            juSet[i].father = i;
            juSet[i].height = 0;
        }
        for (int i = 0; i < numV; i++)
            for (int j = 0; j <= i; j++)
            {
                int w;
                scanf("%d", &w);
                if (i != j && w != -1)
                {
                    edgeSet[numE].u = i;
                    edgeSet[numE].v = j;
                    edgeSet[numE].w = w;
                    numE++;
                }
            }
        printf("%d\n", Kruskal(numV, numE));
    }
    return 0;
}