洛谷刷题笔记 其二

洛谷笔记2

1.邻接表

有关树类型的问题基本上都可以用邻接表来表示

当出现图的连续关系的时候，可以用一个数组adj[i] [i+1]来表示节点i的下面有的根节点

1
2
3
int adj[i+1][i]//表示i+1(i是从0开始)节点下面的某些节点
int adj_size[i+1]//表示i+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
//比如：
/*
输入：最大数为8,9行
1 2
1 3
1 4
2 5
2 6
3 7
4 7
4 8
7 8
*/
int adj[9][8];
int adj_size[9];
for(int i=1;i<=9;++i){
    int x,y;
    scanf("%d,%d",&x,&y);
    adj[x][adj_size[x]++]=y;//这样就构造出来了一个邻接表
}
//注意：
这里还要后续对每个节点进行排序
for(int i=1;i<=n;++i){
    qsort(adj[i],adj_size[i];sizeof(int),1);
}

dfs在邻接表中的应用(dfs应用：一是标记搜索，二是回溯搜索)

1
2
3
4
5
6
7
8
9
10
11
12
//假如现在有个树状图，已经用邻接表构造出来了，现在要用dfs搜索这个图，并且要求如果遇到相同的节点就停止搜索
int visited[i+1]={0};//标记下每个节点
int dfs(int node){
    visited[node]=1;
    printf("%d",node);
    for(int i=0;i<adj_size[node];++i){
        int next=adj[node][i];
        if(!visited[node]){
            dfs(next);
        }
    }
}

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
36
37
38
39
//现在是有个树状图，同样用邻接表表示出来了，用bfs广度地搜索这个，同样，遇到已经搜索过的节点就停止搜索
//在bfs搜索中常用的方法是队列，先进先出，来实现每层的搜索
//队列就像是排队的人一样，先进先出，而栈，就像一堆盘子，后摆放的（进）先出

//bfs中队列的应用就是：假如：
/*
1
2 3
|  |
4  5
先存入1此时队列[1]
然后访问1
存入1的子节点[2,3]
再访问2--[3,4]注意每次加都是后面加，前面的头节点都是在操作的时候就删除，所以一层前面一个节点访问完后，会弹出，并访问下一个头节点
再访问第2层的3--[4,5]
然后依次访问4,5---[]

*/
int visited[i+1]={0};//特别要注意的是，队列的两个指针front和rear中头指针front随着队列++操作，将不再为0，他们的递增不会是同步的，他们会根据彼此出队front和入队rear的操作变化来形成一个队列的长度
//要注意的是，这样下去，用来维持其操作的数组queue的范围就要比较大，这里一定要开比较大，这时可以用线性的数组或者环形的数组，比较推荐用环形数组，那样空间的浪费比较小（不建议，麻烦）
int bfs(int start){
    int queue[10000];
    int front=0,rear=0;
    queue[rear++]=start;//从尾部rear开始添加新节点start
    visited[start]=1;//标记一下
    while(front<rear){//这里，除非所有节点遍历完，否则队列不会为空
        //上面是添加节点，接下来就是开始取节点操作了
        int node=queue[front++];
        printf("%d"，node)；
        //接下来就是遍历当前的节点的所有子节点，继续添加在队列尾端，下一个while时，这时的尾端又变成了头端
        for(int i=0;i<adj_size[node];++i){
            int next=adj[node][i];
            if(!visited[node]){//没有被标记就添加到队列尾端
                queue[rear++]=next;
            }
        }
    }

}

2.链式向前星邻接表：适用于大范围遍历

链式向前星不用排序，本身就是一个无序的图表示

如下图，这个链表是反过来的

![img](C:\Users\Admin\Documents\Tencent Files\1655299098\nt_qq\nt_data\Pic\2025-02\Ori\25b5177bc90a8343845ad529717858e8.jpeg)

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

int head[max];//储存的是每个点的每条边对应的边的编号，从最开始不断累加
int edge[max];//值表示边max的终点，即1->2，表示的就是->这个边的终点2
int next[max];//next的索引是上一个边，值是下一个边，表示上一个边的下一个边
//总之，next是下一条边的编号，head是上一条的，他们相互更新，然后edge就专门存储边的终点
//---那就是head只是开了个i边的头，next是顺着head记录i点连接的接下来的边（总结）
int cnt;//cnt就是用来记录边号的

inline void init(){//初始化
    for(int i=0;i<max;++i){
        head[i]=next[i]=-1;
    }
    cnt=0;
}
inline void addedge(int u,int v){
    edge[cnt]=v;
    next[cnt]=head[u];
    head[u]=cnt++;
}
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
//对边进行操作
#include<stdio.h>
#include<stdlib.h> 
#include<string.h>
typedef struct{
	int to;
	int next;
}Edge;

Edge edge[200010];
int cnt=0;
int head[100010];
void addadge(int u,int v){
	edge[cnt].to=v;
	edge[cnt].next=head[u];//下一条边，反过来想 
	head[u]=cnt++; 
}
int main(){
	int n,m;
	scanf("%d %d",&n,&m);

	memset(head,-1,sizeof(head));
	for(int i=0;i<m;++i){
		int u,v;
		scanf(" %d %d",&u,&v);
		addadge(v,u);
	}
	int *a=(int *)malloc((n+1)*sizeof(int));
	int *vis=(int *)calloc(n+1,sizeof(int));
	int *queue=(int *)malloc((n+1)*sizeof(int));
	
	for(int i=n;i>=1;--i){
		if(!vis[i]){
			int front=0,rear=0;
			queue[rear++]=i;
			vis[i]=1;
			a[i]=i;
			while(front<rear){
				int u=queue[front++];
				for(int j=head[u];j!=-1;j=edge[j].next){
					int v=edge[j].to;
					if(!vis[v]){
						vis[v]=1;
						a[v]=i;
						queue[rear++]=v;
					}
				}
			}
		}
	}
	for(int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
	free(vis);
	free(a);
	free(queue);
	return 0;
}

3.技巧：大量遍历图的时候

如果题目让我们求一个点出发所能达到的最大点，这样要我们履历每个点，数据一旦多了时间复杂度就非常大

不如等价为：从最大的点开始，统计有哪些点能达到这个最大点

这时，就可以反向地来建边，反向建边推荐用链式向前星

4.技巧：inline内联提升效率

在大量调用一些简短的函数时，可以在前面加上inline，这样编译器就会直接把该函数的代码插入对应位置，提升运行效率，但是，递归这种不知道要递归几次的函数不行

5.技巧：图的最短路径问题：

Dijkstra算法

运用于1点到各个点的最短距离问题

这里通常使用邻接表来存储图，因为不同于Floyd算法是两点之间，这个是一点到各个点，图内比较稀疏

例题：(这道题传统的dijkstra算法好像也做不了，要用到堆优化)

2.蓝桥王国 - 蓝桥云课

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 <stdio.h>
#include <stdlib.h>
long long int path[10002][10002]={{-1}};
int main(){
  long long int n,m;
  scanf("%lld %lld",&n,&m);
  
  long long int st[n];
  for(long long int i=0;i<m;++i){
    long long int u,v,w;
    scanf(" %lld %lld %lld",&u,&v,&w);
    path[u][v]=w;
    path[v][u]=w;
  }
  st[0]=0;
  for(long long int k=2;k<=n;++k){
    for(long long int i=2;i<=n;++i){
      if(path[1][k]>path[1][i]+path[i][k]){
        st[i-1]=path[1][i]+path[i][k];
        path[1][k]=path[1][i]+path[i][k];
      }
      else{
        st[i-1]=path[1][k];
      }
    }
  }
  for(long long int i=0;i<n;++i){
    printf("%lld ",st[i]);
  }
  return 0;
}
*/
//第一个是纯纯暴力的，不行，接下来是还是dijkstra做法，但是效率提升了

//dijkstra算法的基本思路是，假设一个已知最短路径的点为白点。那么，起始状态中，第一个点就是白点，在这基础上，去搜索这个点所连接的下面的一层蓝点，先看看这一系列点能不能根据白点进一步缩短值，这里操作完毕后比较这更新后的一系列点，找出他们最小值的点再次作为白点。这样的过程不断地进行下去，用到贪心的思想，每次都找最小的点，最终得到原点到每个点的最短路径。

//要注意的是：源点到源点的最短路径是0，其他的点的最开始最短路径是0x3f3f3f3f（∞）

详细看10.堆优化

Floyd-Warshall算法

适用于任意两点之间的最短距离

就是在两点之间加上大于1的点作为中转，以求达到最少的路径

例题：（本题还在想）

3.蓝桥王国2 - 蓝桥云课

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
/*下面是我第一次做的代码，七个案例只对了3个，虽然战况有点惨烈，但是还是挺激动的，因为至少我思路是对的，接下来分析细节方面
#include <stdio.h>
#include <stdlib.h>

int compare(const void *a,const void *b){
  return *(int *)a-*(int *)b;
}
int main(){
  int n,m;
  int num=0;
  int s,t,k,st[n+1];
  int j=0;
  scanf("%d %d",&n,&m);
  int path[2*n+2][2*n+2];
  for(int i=0;i<m;++i){
    int u,v,w;
    scanf(" %d %d %d",&u,&v,&w);
    path[u][v]=path[v][u]=w;
  }
  scanf(" %d %d %d",&s,&t,&k);
  for(int p=0;p<n;++p){
    if(path[s][t]>path[s][p]+path[p][t]){
      st[j]=path[s][t]=path[s][p]+path[p][t];
      j++;
    }
  }
  if(j<k) {
    printf("-1");
    return 0;
  }
  qsort(st,j,sizeof(int),compare);
  printf("%d",st[k-1]);
  return 0;
}
*/

6.关于指针的认知澄清

1.结构体中

1
2
3
4
5
6
7
8
9
10
11
12
13
//假如：
tpyedef struct{
    int a;
    int b;
}node;

node *s[100];//这时，这里的s[]存储的都是地址
//此时，例如，当我们给其动态分配下内存
adj[0]=malloc(3*sizeof(node));//这时，就相当于给这一个地址adj[0]开辟了adj[0][0]-[2]三个具体的，可以干活的房间，这三个房间就不是地址了
//那能不能直接node s[][]呢？岂不省事？

//这里，如果只追求静态数组，那可以，不过，要是要动态分配内存的话，需要在一个原有的地址上进行，建房子必须要先有地基嘛，所以就需要了指针数组
//上面的3可以是n，最后对地址(地基)free一下释放下内存就好

2.函数参数中：

1
2
3
4
5
6
7
8
//在函数的参数中，我们知道，参数其实是传递的变量的副本，如果要真实地更改一个变量的值，这时候就要用指针对其地址作为参数
int max(int *a,int *b)
    
//同理，那如果参数是原本是一个指针呢？即我们要对原本的指针做出修改
int *a;
int max(int **a)//这里，参数即一个指向指针的指针，和上面同理，这时，就可以通过函数对外面的指针所代表的值进行操作了，而不是副本
    
//总的来说*一次的时候是对变量的值进行操作，而**两次，是对指针的指针进行操作，即对变量的地址进行操作，这时就可以修改指针指向的地址

7.技巧：堆优化(堆优化是解决大规模最短路径问题的必备技能)

这里建议每次用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
47
48
49
50
51
52
53
54
55
56
57
58
59
//堆顶元素一定是最父的节点
//在使用dijkstra算法中，要运用的是堆这个数据结构来形成的优先队列，所以不一定要求是完全二叉树
//首先是堆操作的代码

tpyedef struct{
    int id;
    long long dist;
}node;//优先队列的节点（堆元素）

node heap[100000];//容器
int heap_size=0;//大小

//插入操作，维护最小堆
void push(int id,long long dist){
    head[head_size].id=id;
    head[head_size].dist=dist;
    //接下来是上浮操作，类似冒泡
    int current=head_size++;
    while(current>0){
        int parent=(current-1)/2;//父节点，在前，比较父节点和当前的节点（子节点）
        if(head[current].dist<head[parent].dist){
            node tmp=head[current];
            head[current]=head[parent];
            head[parent]=tmp;
            current=parent;//继续对本次父节点的父节点进行操作
        }
        else{
            break;
        }
    }
}
//删除堆操作，就是取出堆顶，然后让最后一个堆元素（即最大元素）放在堆顶的位置，接着一直锚定这个元素，对其位置的子节点进行比较，和子节点最小的不断地替换，最终达到一个堆的形态，这个过程叫做下沉。
void pop(){
	node top=heap[0];//先把堆顶存着
    head[0]=head[head_size--];
    
    int current=0;//从堆中第0个元素开始
    while(1){
        int l=current*2+1;
        int r=current*2+2;
        int small=0;//用来比较最小的，下面过程就是用来筛
        if(l<head_size && head[l].dist<head[small].dist){//防越界并规定只能父子比较，经过2层，选出两子节点最小的节点
            small=l;
        }
        if(r<head_size && head[r].dist<head[small].dist){
            small=r;
        }
        if(small!=current){
            node tmp=heap[current];
            heap[current]=heap[small];
            heap[small]=tmp;
            current=small;
        }
        else{
			break;
        }
    }
    return top;//返回最小的元素
}

接下来是堆优化在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
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
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct {
    int v;
    long long w;
} Edge;

typedef struct {
    int u;
    long long dist;
} Node;

Edge *adj[300001];
int adj_size[300001] = {0};
long long dist[300001];
int visited[300001] = {0};

void swap(Node *a, Node *b) {
    Node t = *a;
    *a = *b;
    *b = t;
}

void heapify(Node *heap, int size, int i) {
    int smallest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && heap[l].dist < heap[smallest].dist) smallest = l;
    if (r < size && heap[r].dist < heap[smallest].dist) smallest = r;
    if (smallest != i) {
        swap(&heap[i], &heap[smallest]);
        heapify(heap, size, smallest);
    }
}

void push(Node *heap, int *size, Node node) {
    heap[(*size)++] = node;
    for (int i = (*size)/2 - 1; i >= 0; --i)
        heapify(heap, *size, i);
}

Node pop(Node *heap, int *size) {
    Node res = heap[0];
    heap[0] = heap[--(*size)];
    heapify(heap, *size, 0);
    return res;
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; ++i) {
        int u, v;
        long long w;
        scanf("%d %d %lld", &u, &v, &w);
        adj_size[u]++;
        adj[u] = realloc(adj[u], adj_size[u] * sizeof(Edge));
        adj[u][adj_size[u]-1] = (Edge){v, w};
    }
    for (int i = 1; i <= n; ++i)
        dist[i] = LLONG_MAX;
    dist[1] = 0;
    Node heap[m];
    int heap_size = 0;
    push(heap, &heap_size, (Node){1, 0});
    
    while (heap_size > 0) {
        Node node = pop(heap, &heap_size);
        int u = node.u;
        
        if (visited[u]) continue;
        visited[u] = 1;
        
        for (int i = 0; i < adj_size[u]; ++i) {
            int v = adj[u][i].v;
            long long w = adj[u][i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                push(heap, &heap_size, (Node){v, dist[v]});
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (dist[i] == LLONG_MAX)
            printf("-1 ");
        else
            printf("%lld ", dist[i]);
    }
    for (int i = 1; i <= n; ++i)
        free(adj[i]);
    
    return 0;
}

8.memset–string.h

1
2
3
//用于将一块内存的值设定为指定的值，这块内存可以是数组，字符串等等
int a[n];
memset(a,-1,n);