ray52033

学习笔记

比赛题解(7) 题解(13)

/ 注册

全部文章 / 学习笔记（共4篇）

学习笔记4（最短路）

dijkstra:求单源最短路算法步骤: 1. 找离起点x最近的未讨论过的点k。 2. 判断经过k点，起点x到其他点的距离是否缩短，如缩短则更新。将k点标记为已讨论。 3. 重复进行第1步，直到所有点都被讨论过为止。于是我们可以得出: dis[i]=min{dis[k]+Map[k][i]} ...

2020-01-04

1 689

学习笔记1（最小生成树）

最小生成树 Kruskal算法：（找最小生成树）首先按照边的长度由小到大排序每次选出最小的与之前选过的判断在不在同一集合（并查集）如果m条边都枚举完还没连到n-1条边，则无解。时间复杂度 O(mlogm) (m为边的数量) 代码： #include<stdio.h> #incl...

2020-01-04

1 595

学习笔记2（图的连通性）

图的遍历方法一：宽搜 queue<int> q; void bfs(int s){ q.push(s); mark[s]=1; while(q.size()){ int x=q.front(); q.pop(); ...

2020-01-04

1 490

（学习笔记3）差分数组

引例：数列游戏（NKOJ3754）给定一个长度为N的序列，首先进行A次操作，每次操作在Li和Ri这个区间加上一个数Ci。然后有B次询问，每次询问Li到Ri的区间和。初始序列都为0。第一行三个整数N A B。(1<=N<=1000000,1<=A<=N,A<=B...

2020-01-04

1 749