有关于在题目中,图的存储 和图进一步的学习

图的存储

直接存边

由于直接存边的遍历效率低下,一般不用于遍历图。

在 Kruskal 算法 中,由于需要将边按边权排序,需要直接存边

1
2
3
4
struct edge{
int x, y;
int w;
}e[maxn];

邻接矩阵

一个二维数组 adj 来存边,其中 adj[u][v] 为 1 表示存在uuvv的边,为 0 表示不存在。如果是带边权的图,可以在 adj[u][v] 中直接存储权值大小

邻接表

使用一个支持动态增加元素的数据结构构成的数组,如 vector adj[n + 1] 来存边,其中 adj[u] 存储的是点 uu的所有出边的相关信息(终点、边权等)。

例如在有向图中,遍历一个节点的左右儿子节点,我们可以直接采用循环的 for(int i = 1; i <= adj[u].size(); i++)来遍历

最小生成树

采用kruskal算法,其中思路很简单.思路很简单,为了造出一棵最小生成树,我们从最小边权的边开始,按边权从小到大依次加入,如果某次加边产生了环,就扔掉这条边,直到加入了n1n- 1条边,即形成了一棵树 时间复杂度为 O(ElogV)O(ElogV)

下面给出伪代码步骤:

1
2
3
4
5
6
7
8
init(p[maxn]);
for i in range(0, m):
if (p[from_point] != p[to_point]):
merge(from_point, to_point)
ans += e[i].wight
time ++
if (time == n - 1):
break

例题: https://www.luogu.com.cn/problem/P3366

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
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200020;
int p[5010];
int n, m;

struct edge {
int x, y;
int w;
}e[maxn];

bool cmp(edge x, edge y) { return x.w < y.w; }
int find(int x) { return p[x] == x ? x : p[x] = (find(p[x])); }

void kruskal() {
int ans = 0, sum = 0;
for (int i = 0; i < m; i++) {
int x = find(e[i].x); int y = find(e[i].y);
if (x != y) {
ans += e[i].w; p[x] = y;
sum++;
}
if (sum == n - 1) break;
}
cout << ans;
}

int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) { cin >> e[i].x >> e[i].y >> e[i].w; }
for (int i = 0; i < n; i++) p[i] = i;
sort(e, e + m, cmp);
kruskal();
return 0;
}

例题: https://www.luogu.com.cn/problem/P2872

这题怎么说呢,有点坑人.sqrt哪里有精度要求,此外对于这种节点编号从1开始,而你又是从0开始存储的这种情况,最好在一开始就统一,要么全部从1开始,要么全部从0开始然后此后的输入编号都要减1

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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 50001000;

struct nodes {
int x, y;
} node[maxn];

struct edge {
int x, y;
double w;
}e[maxn];

int n, m, cnt = -1, p[maxn];

bool cmp(edge a, edge b) {
return a.w < b.w;
}

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

int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> node[i].x >> node[i].y;
for (int i = 0; i < n; i++) p[i] = i;

for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int x = node[i].x - node[j].x; int y = node[i].y - node[j].y;
e[++cnt].w = (double)(sqrt((double)(x * x) +(double)(y * y))); e[cnt].x = i; e[cnt].y = j;
}

for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
e[++cnt].x = x - 1; e[cnt].y = y - 1;
e[cnt].w = 0;
}

sort(e, e + cnt , cmp);
double ans = 0; int sum = 0;
for (int i = 0; i < cnt; i++) {
int x = find(e[i].x); int y = find(e[i].y);
if (x != y) {
ans += e[i].w; p[x] = y;
sum++;
}
if (sum == n - 1) break;
}
printf("%.2lf", ans);
return 0;
}

例题 : https://www.luogu.com.cn/problem/P2820 最后减去权值和即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for (int i = 0; i < m; i++){
cin >> e[i].x >> e[i].y >> e[i].w;
sumf += e[i].w;
if (e[i].w == 0) e[i].w = 1010;
}

for (int i = 0; i < n; i++) p[i] = i;
sort(e, e + m, cmp);
int sum = 0, ans = 0;
for (int i = 0; i < m; i++){
int x = find(e[i].x); int y = find(e[i].y);
if (x != y){
ans += e[i].w;
p[x] = y;
sum ++;
}
if (sum == n - 1) break;
}
cout << sumf - ans;

最短路径

Floyd 算法 O(n3)O(n^{3})

第一次看floyd的时候很简单,以为自己理解了,但是回过头来再看的时候,发现虽然简单,但是仍然需要时间理解的.floyd算法思想是基于动态规划,假设i到 j经过k-1个点的最短路径已经找出,则经过k个点的方程可以求出来

f[k][i][j]=min(d[k1][i][j],d[k1][i][k]+d[k1][k][j])f[k][i][j]=\min (d[k-1][i][j], d[k-1][i][k]+d[k-1][k][j])

但我们发现数组的第一维是没有用的,于是可以直接改成

f[i][j]=min(d[i][j],d[i][k]+d[k][j])f[i][j]=\min (d[i][j], d[i][k]+d[k][j])

给出代码

1
2
3
4
for (k = 1; k <= n; k++) 
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);

最小环

采用Floyd算法,因为我们可以计算i到 j 的最短路径,那么我们可以找到另外一点k使得 d[i][j]+di[i][k]+d[k][j]d[i][j] + di[i][k]+ d[k][j] 最小即可

例题: https://www.luogu.com.cn/problem/P6175

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
#include <iostream>
#include <algorithm>

using namespace std;
const int maxn = 110;
const int INF = 1e7;

int n, m, ans = INF;
int dis[maxn][maxn], d[maxn][maxn];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i == j) dis[i][j] = d[i][j] = 0;
else dis[i][j] = INF; d[i][j] = INF;
}

for (int i = 1; i <= m; i++) {
int x, y, w; cin >> x >> y >> w;
d[x][y] = d[y][x] = w;
dis[x][y] = dis[y][x] = w;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
ans = min(ans, dis[i][j] + d[i][k] + d[k][j]);
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++) {
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
dis[j][i] = dis[i][j];
}
}
if (ans == INF) cout << "No solution.";
else cout << ans;
return 0;
}

二叉树树的存储

  • 结构体
  • a[2 * i] 和 a[2 * i + 1]分别表示左右子树

例题 : https://www.luogu.com.cn/problem/P4913

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

const int maxn = 1e6 + 10;
struct tree {
int l, r;
}t[maxn];
int n;
int dfs(int x) {
if (x == 0) return 0;
return max(dfs(t[x].l), dfs(t[x].r)) + 1;
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x, y; cin >> x >> y;
t[i].l = x; t[i].r = y;
}
cout << dfs(1);
return 0;
}

树的重构与遍历

输入节点信息,输出其某个遍历, 第一个字符为后面两个字符的根节点

a b d \n b e f

首先知道erase的用法string & erase (size_t pos = 0, size_t len = npos);所以得出以下代码

但是一下并不是一个通用方案,因为它会给出根节点所以比较取巧而已.正确做法还得是将字符转为数字,

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(){
cin >> n;
string first;cin >> first;
for (int i = 0; i < n - 1; i++){
string str; cin >> str;
int pos = first.find(str[0]);
first.erase(pos, 1);
first.insert(pos, str);
}
for (int i = 0; i < first.size(); i++)
if (first[i] != '*') cout << first[i];
return 0;
}

输入中序 和 后序遍历,输出其先序遍历

需要说明的是find()返回下标,substr函数第二个参数为长度,若只有一个参数,则表示截取参数位置到字符串末尾

本题为什么可以直接在中间输出root,而不需要重构之后在输出呢.因为这个函数顺序结构导致了其递归的时候也是此顺序结构.因为模式相同,在最后的的叶子节点的递归基返回的时候,同样是输出根,左子树,右子树.所以如果给出中序 和 先序遍历 也可以输出后序遍历

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
#include <iostream>
using namespace std;

string in, post;
void build(string a, string b){
if (a.size() > 0){
char root = b[b.size() - 1];
cout << root; \\根
int rootindex = a.find(root);
build(a.substr(0,rootindex), b.substr(0,rootindex)); \\左子树
build(a.substr(rootindex + 1), b.substr(rootindex, b.size() - rootindex - 1));
}
}
void build_post(string a, string b){
if (a.size() > 0){
char root = b[0];
int rootindex = a.find(root);
build_post(a.substr(0, rootindex), b.substr(1, rootindex));\\左子树
build_post(a.substr(rootindex + 1), b.substr(rootindex + 1)); \\ 右子树
cout << root; \\ 根
}
}
int main(){
cin >> in >> post;
build(in, post);
return 0;
}

另外一个有趣的问题是,如果知道前序和后序遍历,那么中序遍历有多少种可能呢? 只有一个儿子 的节点 才会在知道 前序后序 的情况下有不同的中序遍历,所以将题目转化成找 只有一个儿子的节点个数.可以很容易的找出这类节点在前序后序中出现的规律。(前序中出现AB,后序中出现BA,则这个节点只有一个儿子) 每个这类节点有两种中序遍历(及儿子在左,儿子在右)根据乘法原理中序遍历数为 2^节点个数种

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>

using namespace std;
int main(){
string a, b; int ans = 0;
cin >> a >> b;
for (int i = 0; i < a.size(); i++)
for (int j = 1; j < b.size(); j++)
if (a[i] == b[j] && a[i + 1] == b[j - 1])
ans ++;
cout << (1 << ans) ;
return 0;
}

树状数组

线段树

建树

1
2
3
4
5
6
7
8
9
10
11
void build(int s, int t, int p) {
// 对 [s,t] 区间建立线段树,当前根的编号为 p
if (s == t) {
d[p] = a[s];
return;
}
int m = (s + t) / 2;
build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
// 递归对左右区间建树
d[p] = d[p * 2] + d[(p * 2) + 1];
}

区间查询

1
2
3
4
5
6
7
8
9
10
11
int getsum(int l, int r, int s, int t, int p) {
// [l,r] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
if (l <= s && t <= r)
return d[p]; // 当前区间为询问区间的子集时直接返回当前区间的和
int m = (s + t) / 2, sum = 0;
if (l <= m) sum += getsum(l, r, s, m, p * 2);
// 如果左儿子代表的区间 [l,m] 与询问区间有交集,则递归查询左儿子
if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
// 如果右儿子代表的区间 [m+1,r] 与询问区间有交集,则递归查询右儿子
return sum;
}

评论




Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

loading...loading... , total visits times