正式进入代码模板2-数据结构专题。
单调队列（滑动窗口）
滑动窗口题目总结：
首先考虑用一个普通队列怎么做？（实际上就是滑动窗口使用队列来维护），那么O(n) 是得到了队列，然后队列长度是k，那么总共的时间复杂度是O(nk)
- 普通队列该怎么做
- 将队列中的没有用的元素删掉-> 具有了单调性
- 可以用 O(1) 时间从队头/ 尾取出最值
用处一般只有两处：
- 滑动窗口中的极值
- 找出离他最近的比他小的元素或者最大元素
1
2
3
4
5
6
7
8
|
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}
|
例题
79. 滑动窗口的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
// 单调队列问题， 队列中是递增的，那么队首就是最大值
// 需要维护窗口size 的大小和 保持单调性
// 需要使用双向队列
vector<int> maxInWindows(vector<int>& nums, int k) {
deque<int> q;
vector<int> res;
for(int i =0; i< nums.size(); i++ )
{
// 维持窗口的大小
while(q.size() && q.front() <= k-i) q.pop_front();
// 维持单调性
while(q.size() && nums[i] >= nums[q.back()]) q.pop_back();
q.push_back(i);
if(q.front() +1>= k) res.push_back(nums[q.front()]);
}
return res;
}
};
|
这个是单机版本
时间复杂度是$O(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
|
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{
int n, k;
vector<int> arr;
cin>>n>>k;
for(int i =0; i< n; i++ )
{
int tmp;
cin >> tmp;
arr.push_back(tmp);
}
deque<int> q;
vector<int> res;
for(int i =0; i< n; i++)
{
while(q.size() && i-q.front() +1> k ) q.pop_front();
while(q.size() && arr[i] >= arr[q.back()]) q.pop_back();
q.push_back(i);
if(i-k +1>=0) res.push_back(arr[q.front()]);
}
for(auto u : res)
{
cout << u<<" ";
}
cout << endl;
return 0;
}
|
154. 滑动窗口
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
|
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{
int n,k;
cin >>n>>k;
vector<int> arr;
for(int i =0; i<n; i++)
{
int tmp;
cin >>tmp;
arr.push_back(tmp);
}
deque<int> min_q, max_q;
vector<int> min_r, max_r;
for(int i =0; i< n; i++)
{
// 这个一定要分清谁大谁小
while( max_q.size() &&i- max_q.front() +1 >k) max_q.pop_front();
while(min_q.size() && i- min_q.front() +1> k) min_q.pop_front();
// max_q 是递增的, min_q 是递减的
while(max_q.size() && arr[i] >= arr[max_q.back()]) max_q.pop_back();
while(min_q.size() && arr[i] <= arr[min_q.back()]) min_q.pop_back();
max_q.push_back(i);
min_q.push_back(i);
if(i -k +1 >=0) max_r.push_back(arr[max_q.front()]);
if(i -k +1 >=0) min_r.push_back(arr[min_q.front()]);
}
for(auto u : min_r)
{
cout << u<<" ";
}
cout <<endl;
for(auto u : max_r)
{
cout << u<<" ";
}
cout <<endl;
}
|
Trie字符串统计
为什么使用trie 树，因为trie 树可以快速的（时间复杂度可以 O(n)）判断下面两个事情
- 是否存在一个串， 是当前串的前缀：遍历路径中是否存在字符串结尾标志。
- 当前串，是否是某个串的前缀：遍历路径中， 是否创建过新的节点。
142. 前缀统计
输入的数据大于 100万的话，那么使用 scanf() ，否则使用 cin
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
|
#include<iostream>
using namespace std;
const int N =1e6+11, M =5e5;
int n, m;
// 使用数组的方式存储trie,也是可以使用结构体的方式
int son[M][26], cnt[N], idx;//cnt 表示以当前节点为终点的单词的个数, idx 是遍历的指针
char str[N];
void insert()
{
int p =0; // 一般使用 0号节点表示根节点
for(int i=0; str[i]; i++ )
{
// 首先搞到当前节点的儿子
int &s =son[p][str[i] -'a'];
if(!s) s = ++ idx;// 如果不存在的话，那就重新分配一个新的指针
p =s;
}
// 最后p就是终点，
cnt[p] ++; // 这个是统计的时候，以当前的点为终点的个数
}
int query()
{
int p =0, res =0;
for(int i =0; str[i] ; i++)
{
int &s =son[p][str[i] -'a'];
if(!s) break;
p =s;
res += cnt[p];
}
return res;
}
int main()
{
scanf("%d%d", &n, &m); // 如果大于 100万
while(n --)
{
scanf("%s", str);
insert();
}
while(m --)
{
scanf("%s", str);
printf("%d\n", query());
}
return 0;
}
|
161. 电话列表
这个比较难， 可以接着看
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
|
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N =100010;
int n ;
int son[N][10], idx;
char str[10010];
bool f[N];
// 需要判断两个内容
bool insert(char * str)
{
int p =0;
bool is_match =false;
bool has_new_node =false;
for(int i =0; str[i]; i++)
{
int u =str[i] -'0';
if( !son[p][u])
{
son[p][u] = ++idx;
has_new_node =true;
}
p =son[p][u];
if(f[p]) is_match =true;
}
f[p] =true;
return !is_match && has_new_node;
}
int main()
{
int T;
cin >> T;
// vector<int> 其实也是可以exactly 的初始化
// 对于 数组这样进行初始化,
while(T--)
{
cin >>n;
memset(son, 0, sizeof son);
memset(f, false, sizeof f);
idx =0;
bool res =true;
for(int i =0; i< n; i++)
{
cin >> str;
if(!insert(str)) res =false;
}
if(res ) puts("YES");
else puts("NO");
}
return 0;
}
|
搜索和图论
决定我们采用邻接矩阵还是采用邻接表来表示图，需要判断一个图是稀疏图还是稠密图。稠密图和稀疏图的判断是边数和顶点树的关系，如果点数少，边数多，那么就是稠密图，反之就是稀疏图。具体关系，邻接矩阵适用于稠密图（边数接近于顶点数的平方）这种f，邻接表适用于稀疏图（边数远小于顶点数的平方）。据说：邻接表是表示图的标准方法，原因是稠密图在实际应用中并不多见。因为稠密图用邻接表表示的话会占用很多空间，而邻接矩阵的空间是固定的都是n²，所以用矩阵表示稠密图。
问题解释：
从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径，称为最短路径
算法特点：
迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
从顶点v1到其他各个顶点的最短路径
百度过后仿佛打开了新世界的大门，头文件居然还可以这样用！！
1
|
#include<bits/stdc++.h> // 万能头文件， 如果不背会 那才是傻逼
|
Dijkstra求最短路 I
比较好的讲解
朴素dijkstra算法 时间复杂是 $O(n^2+m)$， $n$表示点数，$m $表示边数
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
|
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N]; // true表示已经确定最短路
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 迭代n次，每次可以确定一个点到起点的最短路
for (int i = 0; i < n; i++)
{
// 找到当前没有确定最短路的点中距离最小的那个
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[j] < dist[t]))
t = j;
st[t] = true;
// 用t更新其他未确定最短路的点的到起点的距离
for (int j = 1; j <= n; j++)
if (!st[j]) // if可加可不加
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
if (dist[n] == 0x3f3f3f3f) return -1; // 1与n不连通
return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c); // 有重边保留短的一条
}
cout << dijkstra() << endl;
return 0;
}
|
memset详解 设置无穷大INF
通常情况下在 图计算中的初始化都是使用 0x3f 而不是 0x7fffff（int 所能表示的最大值）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
Memset中无穷大常量的设定技巧
如果问题中各数据的范围明确，那么无穷大的设定不是问题，在不明确的情况下，很多程序员都取0x7fffffff作为无穷大，因为这是32-bit int的最大值。如果这个无穷大只用于一般的比较（比如求最小值时min变量的初值），那么0x7fffffff确实是一个完美的选择，但是在更多的情况下，0x7fffffff并不是一个好的选择。
很多时候我们并不只是单纯拿无穷大来作比较，而是会运算后再做比较，例如在大部分最短路径算法中都会使用的松弛操作：
if (d[u]+w[u][v]<d[v]) d[v]=d[u]+w[u][v];
我们知道如果u,v之间没有边，那么w[u][v]=INF，如果我们的INF取0x7fffffff，那么d[u]+w[u][v]会溢出而变成负数，我们的松弛操作便出错了，更一般的说，0x7fffffff不能满足“无穷大加一个有穷的数依然是无穷大”，它变成了一个很小的负数。
除了要满足加上一个常数依然是无穷大之外，我们的常量还应该满足“无穷大加无穷大依然是无穷大”，至少两个无穷大相加不应该出现灾难性的错误，这一点上0x7fffffff依然不能满足我们。
所以我们需要一个更好的家伙来顶替0x7fffffff，最严谨的办法当然是对无穷大进行特别处理而不是找一个很大很大的常量来代替它（或者说模拟它），但是这样会让我们的编程过程变得很麻烦。在我读过的代码中，最精巧的无穷大常量取值是0x3f3f3f3f，我不知道是谁最先开始使用这个精妙的常量来做无穷大，不过我的确是从一位不认识的ACMer(ID:Staginner)的博客上学到的，他/她的很多代码中都使用了这个常量，于是我自己也尝试了一下，发现非常好用，而当我对这个常量做更深入的分析时，就发现它真的是非常精巧了。
0x3f3f3f3f的十进制是1061109567，也就是10^9级别的（和0x7fffffff一个数量级），而一般场合下的数据都是小于10^9的，所以它可以作为无穷大使用而不致出现数据大于无穷大的情形。
另一方面，由于一般的数据都不会大于10^9，所以当我们把无穷大加上一个数据时，它并不会溢出（这就满足了“无穷大加一个有穷的数依然是无穷大”），事实上0x3f3f3f3f+0x3f3f3f3f=2122219134，这非常大但却没有超过32-bit int的表示范围，所以0x3f3f3f3f还满足了我们“无穷大加无穷大还是无穷大”的需求。
最后，0x3f3f3f3f还能给我们带来一个意想不到的额外好处：如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))这样的代码来实现（方便而高效），但是当我们想将某个数组全部赋值为无穷大时（例如解决图论问题时邻接矩阵的初始化），就不能使用memset函数而得自己写循环了（写这些不重要的代码真的很痛苦），我们知道这是因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0，现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。
所以在通常的场合下，0x3f3f3f3f真的是一个非常棒的选择。
|
堆优化版dijkstra —— 模板题 AcWing 850. Dijkstra求最短路 II
时间复杂度 $O(mlogn) $, $n $表示点数，$m$表示边数， 从时间复杂度角度分析为什么这种是比较优秀的算法，因为 $n$ （点数）远远大于 $m$ ，所以经过 log 处理之后，最后时间复杂度是比较令人满意的。
这个时间复杂度不知道是怎么分析出来的？
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
|
#include<bits/stdc++.h>
using namespace std;
int m, n;
struct Node{
int vec;
int w;
};
const int N =1e5+11;
bool vis[N];
int dis[N];
vector<Node> g[N];
typedef pair<int, int> P;
void dijkstra()
{
// 初始化
memset(vis, 0, sizeof vis);
for(int i =1; i<=m ; i++) dis[i] =INT_MAX;
dis[1] =0;
priority_queue<P, vector<P>, greater<P>> heap;
heap.push({0, 1}); // 第一个维度是 distance, 第二个维度是 vec
while(heap.size())
{
auto t =heap.top();
heap.pop();
int vec =t.second;
int distance =t.first;
if(vis[vec] ==1) continue;
vis[vec] =1;
for(int i =0; i< g[vec].size() ; i++)
{
int next_node =g[vec][i].vec;
if(distance+ g[vec][i].w < dis[next_node])
{
dis[next_node] =distance + g[vec][i].w;
heap.push({dis[next_node], next_node});
}
}
}
}
int main()
{
cin >>m >>n; //m 个点， n 个边
Node tmp;
int a, b, c;
for(int i =0; i< n; i++)
{
cin >> a>> b>> c;
tmp.vec =b;
tmp.w =c;
g[a].emplace_back(tmp);
}
dijkstra();
if(dis[m] ==INT_MAX) cout << -1 << endl;
else cout << dis[m] << endl;
return 0;
}
|
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
|
#include<bits/stdc++.h>
using namespace std;
int m, n; // 表示m 个边， n个点
// 定义一个结点，
struct node{
int index;
int w;
};
const int N =100010;
bool vis[N];
int dis[N];
vector<node> g[N];
typedef pair<int, int> P;
// 迪杰斯特拉算法
void dijkstra()
{
// 初始化
memset(dis, INT_MAX, sizeof dis);
dis[1] =0;
memset(vis, 0, sizeof vis);
// 朴素dijstra算法 时间复杂度 O(n^2+m) n表示点数， m 表示边数
// 使用小根堆优化时间复杂度为O(mlogn) m表示边数 n 表示点数
// 使用小根堆
priority_queue<P, vector<P>, greater<P>> heap;
heap.push({0, 1});
while(heap.size())
{
auto t =heap.top();
heap.pop();
int ver =t.second;
int d =t.first;
// 这个优化一下
if(vis[ver] ==1) continue;
vis[ver] =1;
for(int i =0; i< g[ver].size(); i++)
{
int nex_node =g[ver][i].index;
if(d +g[ver][i].w < dis[nex_node] && vis[nex_node] ==0)
{
dis[nex_node] = d + g[ver][i].w;
heap.push({dis[nex_node], nex_node});
}
}
}
}
int main()
{
cin>> n >>m;
int x, y, z;
node tmp;
for(int i =0; i<m ; i++)
{
cin >>x>>y>>z;
tmp.index =y;
tmp.w =z;
g[x].push_back(tmp);
}
dijkstra();
for(int i =0; i<=n ; i++) cout << dis[i] << " ";
if(dis[n] !=INT_MAX) cout << dis[n]<< endl;
else cout << -1<< endl;
return 0;
}
|
cpp 中默认是大根堆，可以通过设置( greater 参数和 small_heap 正好是相反的)
1
2
|
//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue<int,vector<int>,greater<int> > small_heap;
|
//emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配。emplace函数在容器中直接构造元素。传递给emplace函数的参数必须与元素类型的构造函数相匹配。
// emplace相关函数可以减少内存拷贝和移动。当插入rvalue，它节约了一次move构造，当插入lvalue，它节约了一次copy构造。
787. Cheapest Flights Within K Stops
这个是双关键字的 dijkstra 算法， 讲解
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
|
struct Node{
int no, stops; // 可以理解为双关键字
int distance;
Node(int no_, int stops_, int distance_): no(no_), stops(stops_), distance(distance_) {}
// 在结构体中，就是这样使用的
bool operator >(const Node &other) const {
return distance > other.distance;
}
};
class Solution {
public:
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
//const int INF =1e9;
vector<vector<pair<int, int>>> graph(n); // 这个是邻接矩阵
for(auto &v :flights)
graph[v[0]].emplace_back(v[1], v[2]);
K ++;
vector<vector<int>> dis(n, vector<int>(K +1,INT_MAX ));
vector<vector<bool>> vis(n, vector<bool>(K +1, false));
priority_queue<Node, vector<Node>, greater<Node>> q;
q.push(Node(src, 0, 0));
dis[src][0] =0;
while(q.size())
{
auto u =q.top();
q.pop();
// 这里体现了双关键字
if(vis[u.no][u.stops] ) continue;
vis[u.no][u.stops] =true;
for(const auto &v : graph[u.no])
if(u.stops +1 <=K && dis[u.no][u.stops] + v.second < dis[v.first][u.stops +1]){
dis[v.first][u.stops +1] =dis[u.no][u.stops] +v.second;
q.push(Node(v.first, u.stops+1, dis[v.first][u.stops +1]));// 这种双关键字就不太好容易理解了
}
}
int ans =INT_MAX;
for(int i =1; i<=K ; i++)
{
ans =min(ans, dis[dst][i]);
}
if(ans ==INT_MAX)
ans =-1;
return ans;
}
};
|
floyd算法 —— 模板题 AcWing 854. Floyd求最短路
时间复杂度是 $O(n^3)$, $n$表示点数
简单的说就是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N3)，空间复杂度为O(N2)。
1.dijkstra算法,最经典的单源最短路径算法 上篇文章已经讲到
2.bellman-ford算法,允许负权边的单源最短路径算法
3.spfa,其实是bellman-ford+队列优化,其实和bfs的关系更密一点
4.floyd算法,经典的多源最短路径算法
单源就是从一个点到所有其他点的最短路径，得到的结果是一个数组，表示某个点到其他点的最短距离。常用的算法有Dijkstra算法和Bellmanford算法。
多源最短路径计算所有点到其他点的最短距离，得到的是一个矩阵。常用的算法有Floyd算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
初始化：
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]);
}
|
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
|
#include<bits/stdc++.h>
using namespace std;
const int N =210, INF =0x3f3f3f3f; // 这个在竞赛中是非常常见的
int d[N][N];
int n, m , Q;
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]);
}
int main()
{
cin >> n>>m>> Q;
// 初始化
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;
}
while(m --)
{
int a, b,c;
cin >> a>>b>>c;
d[a][b] =min(d[a][b], c);
}
floyd();
while(Q --)
{
int a, b;
cin >> a>>b;
if(d[a][b] > INF/2) puts("impossible");
else cout << d[a][b] << endl;
}
return 0;
}
|
朴素版prim算法 —— 模板题 AcWing 858. Prim算法求最小生成树
时间复杂度是 $O(n^2+m)$, $n$ 表示点数，$m$ 表示边数
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
|
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通，则返回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;
}
|
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
|
#include<bits/stdc++.h>
using namespace std;
const int N =211;
const int M =2e4+11;
int arr[N][N];
const int INF =0x3f3f3f3f;
int n, m, q;
void floyd()
{
for(int k =1; k<=n ; k++)
{
for(int i =1; i<=n ; i++)
{
for(int j =1; j<=n ; j++)
if(arr[i][k] + arr[k][j] < arr[i][j])
arr[i][j] = arr[i][k] + arr[k][j];
}
}
}
int main()
{
cin >>n >>m >>q;
// init
for(int i= 1; i<=n ; i++)
for(int j =1; j<=n ; j++)
if(i ==j) arr[i][j] =0;
else arr[i][j] =INF;
while(m --)
{
int a, b, c;
cin >> a>> b>>c;
arr[a][b] =min(arr[a][b], c);
}
floyd();
while(q--)
{
int a, b;
cin >> a>>b;
// 这个判断条件是非常巧妙的 if(INF > INF/2) , 这个是yes 的操作， 因为本身的 inf ++ -- 是不会影响最后的结果
if(arr[a][b] > INF/2) puts("impossible");
else cout << arr[a][b]<< endl;
}
return 0;
}
|
Kruskal算法 —— 模板题 AcWing 859. Kruskal算法求最小生成树
时间复杂度是 $O(mlogm)$, $n $表示点数，$m$表示边数
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
|
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;
}
|