Neo's Blog

不抽象就无法深入思考
不还原就看不到本来面目!

0%

Posted on Edited on In Valine:

二叉堆，包括最大堆、最小堆

最大特点：在$O(1)$时间内找到最小（最大）元素

堆的常见应用：

  1. 堆排序
  2. 用两个堆（一个最大堆，一个最小堆）来维护/查询第K大/小的操作
  3. 贪心算法优化
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
堆 —— 模板题 AcWing 838. 堆排序, AcWing 839. 模拟堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b)
{
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

Posted on Edited on In Valine:

给定一个长度为 n+1 的数组nums，数组中所有的数均在 1∼n 的范围内，其中 n≥1。

请找出数组中任意一个重复的数，但不能修改输入的数组。

样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

思考题：如果只能使用 O(1) 的额外空间，该怎么做呢？

思考： 把肯定不符合条件的一半给忽略掉；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int l = 1, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;  //[l, mid], [mid + 1, r]
            int s = 0;
            //注意这里是遍历了所有的元素
            for (int i = 0; i < nums.size(); ++i) s += (nums[i] >= l && nums[i] <= mid);
            if (s > (mid - l + 1)) r = mid;
            else l = mid + 1; //数量不够，说明这个区间内的某个数肯定被替换掉了，所以肯定在另外一边。
        }
        
        return r;
    }
};

Posted on Edited on In Valine:

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例
给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) 
            if (nums[i] < 0 || nums[i] > n - 1) return -1;
        
        for (int i = 0; i < n; ++i) {
            while (i != nums[i]) {
                int x = nums[i];
                if (nums[x] == x) return x; //如果坑位已经被占了，说明重复了。
                else swap(nums[x], nums[i]);
            }
        }
        x
        return -1;
    }
};

Posted on Edited on In Valine:

根据1到m生成1到n随机数

问题1： 给定一个函数rand()能产生1到m之间的等概率随机数，产生1到n之间等概率的随机数？

1
2
3
4
5
6
7
8
9
int rand10()
{
int x;
do
{
    x = (rand7()-1)*7+rand7();
}while(x > 40)  //【1, 40】的范围
return (x-1） / 4+1; //分为10段，0～9 + 1 =》 1 ～ 10
}

考虑如果rand（）返回的是浮点呢？

这种情况下可以简化为，如何把[a,b]线段上的点等概率的映射到[c,d]

另外， 为啥不能考虑rand（） * rand()呢？

因为不等概率，76与67的计算结果都是42，这样子就使得出现42的概率是1/49 + 1/49；出现1的概率是1/49。

参考：

https://www.cnblogs.com/double-win/archive/2014/04/07/3650314.html

https://my.oschina.net/u/4401597/blog/4038277

p & 1 -p 生成等概率

问题2： 有一个随机生成器randA()，以p的概率返回0，1-p的概率返回1，利用这个randA()构造randB()，使randB()等概率的返回0和1，即0.5的概率返回0，0.5的概率返回1。

分析比较简单： 出现00的概率是p^2; 出现10的概率是p(1-p)，出现01的概率是p(1-p); 出现11的概率是（1-p）^2;

以上，只要丢弃掉00，01的结果； 10与01的出现概率就是相等的；也就各为50%。

1
2
3
4
5
6
7
8
9
10
int randB()
{
int x1, x2;
do
{
    x1 = randA();
    x2 = randA();
}while(x1+x2 != 1)
return x1;
}

已知一随机发生器，产生0的概率是p，产生1的概率是1-p，
现在要你构造一个发生器，
使得它构造0和1的概率均为 1/2；
构造一个发生器，使得它构造1、2、3 的概率均为 1/3； …，
构造一个发生器，使得它构造 1、2、3、…n 的概率均为1/n，要求复杂度最低。

思路：
由于需要产生1/2，而用1位0，或1位1无法产生等概率，
因此，考虑将随机数扩展成2位：
00 pp
01 p(1-p)
10 (1-p)p
11 (1-p)(1-p)
有上述分析知道，01和10是等概率的，因此我们只需要产生01和10就行了。
于是可以，遇到00和11就丢弃，只记录01和10。可以令，01表示0,10表示1，则等概率1/2产生0和1了。
对于n=2，一次性生成两个数字，认为01表示0，10表示1，
其它情况放弃，它们的概率都是p(1-p)；
对于n=3，一次性生成三个数字，认为001表示0，010表示1，100表示2，
其它情况放弃，它们的概率都是pp(1-p)；
对于n=4，一次性生成是个数字，认为0001表示0，0010表示1，0100表示2，1000表示3，
其它情况放弃，它们的概率都是ppp(1-p)；
5为例，此时我们取x=2，因为C(2x,x)=C(4,2)=6是比5大的最小的x，
此时我们就是一次性生成4位二进制，把1出现个数不是2的都丢弃，
这时候剩下六个:0011,0101,0110,1001,1010,1100，
取最小的5个，即丢弃1100，那么我们对于前5个分别编号1到5，
这时候他们的概率都是pp(1-p)*(1-p)相等了。
关键是找那个最小的x，使得C(2x,x)>=n这样能提升查找效率。
因为C(n,i)最大是在i接近n/2的地方取得，此时我有更大比率的序列用于生成，
换句话说被抛掉的更少了，这样做是为了避免大量生成了丢弃序列而使得生成速率减慢，
实际上我之所以将x取定是为了让我取得的序列生成的概率互相相等，
比如C(2x,x)的概率就是[p(1-p)]^x，
互等的样例空间内保证了对应的每个值取得的样例等概率。

Shuffle算法

一个从1到n的序列，随机打乱，保证每个数出现在任意一个位置的概率相同。

基于交换，将a[i]与arr[rand(i, n - 1)]随机交换；

1
2
3
4
5
6
7
8
9
10
11
// 得到一个在闭区间 [min, max] 内的随机整数
int randInt(int min, int max);

void shuffle(int[] arr) {
    int n = arr.length();
    for (int i = 0 ; i < n; i++) {
        // 从 i 到最后随机选一个元素
        int rand = randInt(i, n - 1);
        swap(arr[i], arr[rand]);
    }
}

N个数随机选M

问题3： 程序的输入包含两个整数m和n，其中$m \lt n $。输出是0~n-1范围内m个随机整数的有序列表，不允许重复。从概率的角度来说，我们希望得到没有重复的选择，其中每个选择出现的概率相等。

选出这个序列的概率是：$m/n (m-1) / (n-1) … * (1)/(n-m)$

1
2
3
4
5
6
7
8
9
10
11
12
void generate(int m,int n)
{
int t = m;
for(int i = 0; i < n; i++)
    if(Rand(0,n-1-i) < t) //即以t/(n-i)的概率执行下面的语句
    {
        printf("%d\n",i); //这里打印的是i，一直在增长；所以不会重复！！！
        t--;
    }
}
//随着算法继续，i越大，rand（0，n-1-i)得到的数值越小，就容易被选中，
//如果i已经等于n-1-t了，则后面的必然全不都被选中。

蓄水池采样算法

问题4： 如何数据流中随机选出N个元素

蓄水池采样算法，具体步骤如下：

（1）先把N个坑位填上

（2）对于后面新来的第i元素，做如下概率处理：令X=rand(0, i), i > N

A. 如果X在[0, N]之间，则用swap(X, i)

B. 否则啥也不做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int i = 0;
vector<int> res;
while (cin >> Elem) {
    i++;
    if (i < N) {
        res.push(Elem);
        continue;
    }

    X = rand(0, i); 
    if (X < N) {
        swap(res[X], res[i]);
    }
}

深入一下，分布式蓄水池算法： https://www.jianshu.com/p/7a9ea6ece2af

Probability simulation

You are given a fair coin. Can you design a simple game using the fair coin so that your
probability of winning is p, 0 < p < 1

把p表示为2进制小数；例如0.100011100110101

开始抛硬币，正面1； 反面0，计作s[i]

如果第i次抛出1，而p[i] = 0, 则win；
如果第i次抛出0，而p[i] = 1, 则lose；
如果s[i] == p[i]，则继续新的循环

概率分布

男孩女孩问题

如果一个地区所有人都生了女孩就继续生，直到生出男孩立马停下，这个地区会趋于什么样的男女比例？

1:1 ，几何分布

https://www.zhihu.com/question/355605125

一根绳子分三段，能够合成三角形的概率

线性规划 + 几何概率， 1/4

如果在高速公路上30分钟内到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多

泊松分布模拟故障

https://preshing.com/20111007/how-to-generate-random-timings-for-a-poisson-process/

https://preshing.com/20111118/locks-arent-slow-lock-contention-is/

Posted on Edited on In , Valine:

算法题2：给定k个数组，每个数组都是有序的，且每个数组最大值-最小值<1000，1 < k<1000，求所有数的中位数。

解答思路：

定义一个结构体 NumCount {
int number;
int cnt;
}

预处理所有数据，将原来的数据用NumCount nums[k][1000]来保存。

用一个大顶堆来维护K路的最小值。

时间复杂度：$O(1000 * k)$

Posted on Edited on In Valine:

0,1,2

分为三段：0段、未判定段、2段，用三个指针（s0, cur, s2)指向每一段的当前位置。

s0并不是指向0段的最后一个元素，而是指向最后一个元素的下一个元素。s2类似。

如果A[cur]=0，则s0（其实指向1）,cur互换位置； s0++; cur++;
如果A[cur]=1，则cur++;
如果A[cur]=2,则s2，cur互换位置； s2—; cur不变；

Posted on Edited on In Valine:

有字符串,将所有连续的ac跟单独的b去掉后的字符串：如bbbacccccb->ccc; aacceacdby->edy

时间复杂度O(n) 空间复杂度O(n) —> 时间复杂度O(n) 空间复杂度O(1)

这是本题较好的一种解法，设两个指针cur和loc分别从头开始出发，cur每次移动一格，另一个指针loc保留当前的操作位置，如果cur指向的字符是c且loc指向的是a，则将loc回移一位（ac抵消了），如果遇到其他非b的字符，则将loc处的字符置为cur处的字符（++location），一直进行直到到cur到达字符串尾部，此时取字符串开头到loc指针之间的子串即为本题的解。这种解法妙就妙在loc处的字符是即时更新的，一些边界条件都自动消除了。

参考：
https://www.cnblogs.com/SteelArm/p/12773014.html

Posted on Edited on In , Valine:

输入n个整数，输出出现次数大于等于数组长度一半的数。
输入描述:

每个测试输入包含n个空格分割的n个整数，n不超过100，其中有一个整数出现次数大于等于n/2。
输出描述:

输出出现次数大于等于n/2的数。

解题思路

摩尔投票法的核心就是一一抵消，删除不同的数。

因为要找过半的数，用一个变量count记录读取每个变量变化的次数，一个变量temp记录可能过半的数。

先让count = 1，然后让temp = vec[0]，然后往后遍历一遍。
碰到和temp相同的数就给count++，否则就count—，如果count变成0，就让temp=vec[i] (v数组遍历过程中的当前值),并让count = 1。

如此遍历一遍，因为有一个数过半，所以temp最后肯定存储的是过半的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int cnt = 0;
        int val = -1;
        for (int i = 0; i < nums.size(); ++i) {
            if (!cnt) {val = nums[i];}
            
            if (nums[i] == val) {
                cnt++;
            }
            else {
                cnt--;
            }
        }
        
        return val;
    }
};

参考：
https://www.zhihu.com/question/284969980/answer/440979325

Posted on Edited on In Valine:

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

解题思路：

DFS

Posted on Edited on In Valine:

图的表示

稠密图，邻接矩阵；

稀疏图，邻接表

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

(1) 邻接矩阵：g[a][b] 存储边a->b; a, b是定点的序号，特别浪费空间，适合稠密图。

//稀疏图
(2) 邻接表：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;

// 初始化
idx = 0;
memset(h, -1, sizeof h);

// 添加一条边a->b
void add(int a, int b)
{
    //把b当作value， 插入到链表头
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

DFS && BFS

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
树与图的遍历
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
(1) 深度优先遍历 —— 模板题 AcWing 846. 树的重心

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

(2) 宽度优先遍历 —— 模板题 AcWing 847. 图中点的层次

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

拓扑排序

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
拓扑排序 —— 模板题 AcWing 848. 有向图的拓扑序列
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
bool topsort()
{
    int hh = 0, tt = -1;

    // d[i] 存储点i的入度
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }

    // 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
    return tt == n - 1;
}

最短路问题的解法

算法 解决的问题 算法原理 时间复杂度
dijkstra 单源最短路，稠密图， 正权 找到最小距离，用找到的最小距离更新剩余距离 $O(N^2)$ N为图点的数量
堆优化版dijkstra 单源最短路，稀疏图，正权 借助堆来优化dijkstra算法中的查找最小值操作 $O(N^2)$N为图点的数量
bellman-ford 单源最短路，负边权，限制步数的情形 迭代k次，每次找最小距离 $O(N^2)$ N为图点的数量
SPFA 单源最短路，负边权，判定有没有负环 队列优化 $O(N^2)$ N为图点的数量
floyd 多源汇最短路 动态规划思想，三角不等式 $O(N^3)$ N为图点的数量 
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214

朴素dijkstra算法 —— 模板题 AcWing 849. Dijkstra求最短路 I
时间复杂是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
int g[N][N];  // 存储每条边
int dist[N];  // 存储1号点到每个点的最短距离
bool st[N];   // 存储每个点的最短路是否已经确定

// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    for (int i = 0; i < n - 1; i ++ )
    {
        int t = -1;     // 在还未确定最短路的点中，寻找距离最小的点
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 用t更新其他点的距离
        for (int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], dist[t] + g[t][j]);

        st[t] = true;
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
时间复杂度 O(mlogn)O(mlogn), nn 表示点数，mm 表示边数
typedef pair<int, int> PII;

int n;      // 点的数量
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储所有点到1号点的距离
bool st[N];     // 存储每个点的最短距离是否已确定

// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

Bellman-Ford算法 —— 模板题 AcWing 853. 有边数限制的最短路
时间复杂度 O(nm)O(nm), nn 表示点数，mm 表示边数
注意在模板题中需要对下面的模板稍作修改，加上备份数组，详情见模板题。

int n, m;       // n表示点数，m表示边数
int dist[N];        // dist[x]存储1到x的最短路距离

struct Edge     // 边，a表示出点，b表示入点，w表示边的权重
{
    int a, b, w;
}edges[M];

// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
        {
            int a = edges[j].a, b = edges[j].b, w = edges[j].w;
            if (dist[b] > dist[a] + w)
                dist[b] = dist[a] + w;
        }
    }

    if (dist[n] > 0x3f3f3f3f / 2) return -1;
    return dist[n];
}

spfa 算法（队列优化的Bellman-Ford算法） —— 模板题 AcWing 851. spfa求最短路
时间复杂度 平均情况下 O(m)O(m)，最坏情况下 O(nm)O(nm), nn 表示点数，mm 表示边数
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N];        // 存储每个点到1号点的最短距离
bool st[N];     // 存储每个点是否在队列中

// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    queue<int> q;
    q.push(1);
    st[1] = true;

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    if (dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

spfa判断图中是否存在负环 —— 模板题 AcWing 852. spfa判断负环
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n;      // 总点数
int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边
int dist[N], cnt[N];        // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N];     // 存储每个点是否在队列中

// 如果存在负环，则返回true，否则返回false。
bool spfa()
{
    // 不需要初始化dist数组
    // 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。

    queue<int> q;
    for (int i = 1; i <= n; i ++ )
    {
        q.push(i);
        st[i] = true;
    }

    while (q.size())
    {
        auto t = q.front();
        q.pop();

        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if (cnt[j] >= n) return true;       // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环
                if (!st[j])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }

    return false;
}

floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 O(n3)O(n3), nn 表示点数
初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
     
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

最小生成树问题的解法

算法 解决的问题 算法原理 时间复杂度
prim算法 单源最短路，稠密图， 正权 找到最小距离，用找到的最小距离更新剩余距离 $O(N^2)$ N为图点的数量
kraskal算法 单源最短路，稀疏图，正权 并查集 $O(N^2)$ N为图点的数量 
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

朴素版prim算法 —— 模板题 AcWing 858. Prim算法求最小生成树
时间复杂度是 O(n2+m)O(n2+m), nn 表示点数，mm 表示边数
int n;      // n表示点数
int g[N][N];        // 稠密图 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];     // 存储每个点是否已经在生成树中

稠密图，朴素版prim N^2
稀疏图，heap优化版 mlgn 很少用，用kruakal替代

kruskal mlgm
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        int t = -1;
        for (int j = 1; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        if (i && dist[t] == INF) return INF;

        if (i) res += dist[t];
        st[t] = true;

        for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

Kruskal算法 —— 模板题 AcWing 859. Kruskal算法求最小生成树
时间复杂度是 O(mlogm)O(mlogm), nn 表示点数，mm 表示边数
int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge     // 存储边
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];

int find(int x)     // 并查集核心操作
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal()
{
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b)     // 如果两个连通块不连通，则将这两个连通块合并
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}

如何判定图是不是二分图：DFS遍历，奇数环

二分图匹配：匈牙利算法

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
染色法判别二分图 —— 模板题 AcWing 860. 染色法判定二分图
时间复杂度是 O(n+m)O(n+m), nn 表示点数，mm 表示边数
int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;
        }
        else if (color[j] == c) return false;
    }

    return true;
}

bool check()
{
    memset(color, -1, sizeof color);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}

匈牙利算法 —— 模板题 AcWing 861. 二分图的最大匹配
时间复杂度是 O(nm)O(nm), nn 表示点数，mm 表示边数
int n1, n2;     // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx;     // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N];       // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N];     // 表示第二个集合中的每个点是否已经被遍历过

bool find(int x)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true;
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }

    return false;
}

// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
    memset(st, false, sizeof st);
    if (find(i)) res ++ ;
}