图论 最短路问题
源点-起点 汇点-终点
迪杰斯特拉朴素版1.初始化dist起点为0 其余点为无穷大2.重复n次 每次找到未确定的离起点最短的点t 用t对其它点的距离进行更新3.将点t标记为已确定
[迪杰斯特拉朴素版] [c++]1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include<bits/stdc++.h>using namespace std;const int N=520;int n,m,dist[N],g[N][N];bool st[N];int dj(){ memset(dist,0x3f,sizeof dist); dist[1]=0; //除了起点都初始化为正无穷 for(int i=0;i<n;i++) { int t=-1; for(int j=1;j<=n;j++) { if(!st[j] && ...
图论 拓扑序列 dfsbfs
tips:树是一种特殊的图 是无环连通图
有向图边有方向 如a->b无向图边没有方向 a<->b无向图是特殊的有向图 我们就先理解有向图的储存
1.邻接矩阵 其实就是一个二维数组 g[a][b]就存储a->b 有权重就是权重 没有就是bool值表示有无边 邻接矩阵不能有重边 只能保留一条 这个比较浪费空间
2.邻接表 就是n个节点 每个都开单链表 就跟哈希拉链法一样
每个h[i]链中表示的是连接i结点的所有结点 也就是为每一个点都开一个单链表 里面是无序的所以h[i]存的是n个头结点
[存邻接表] [c++]123456789101112const int N=10010;int h[N],ne[N],e[N],st[N],idx;void add(int a,int b){ e[idx]=b; //存编号 ne[idx]=h[a]; //插入 让此结点的下一结点指向之前的头结点 h[a]=idx; //替换头结点 idx++;}
[树的重心(dfs用法)] [c++]12345678910111213141516 ...
进制转换
十进制转n进制
整数：十进制转二进制： 除以2 反向取余数 直到商为0十进制转八进制： 除以8 反向取余数 直到商为0所以十进制转n进制 只需要除以n 反向取余数直到商为0
小数：乘n取整 顺序输出如0.68十进制转二进制 精确到后五位0.682=1.36 ->10.362=0.72 ->00.722=1.44 ->10.442=0.88 ->00.88*2=1.76 ->1 达到要求的精度
所以0.68D=0.10101B小数部分10->a 11->b以此类推
二进制 八进制 十六进制转化为十进制
整数二进制转化为十进制101112^3 +02^2 +12^1 +12^0=11
小数和整数操作相似 但是小数部分从小数点后一位指数为-1开始依次-2 -3
如八进制0.45转换为十进制48^(-1) + 58^(-2)=0.578125
由浅入深dp1.0
顺序： 暴力搜索 -> 记忆化搜索 -> 递推
记忆化搜索=暴力+记录答案递推公式=dfs向下递归公式递归数组初始值=递归的边界
用mem存已经有的值
[上台阶1] [c++]123456789101112131415161718192021222324#include<bits/stdc++.h>using namespace std;long long n;int mem[10000];int dfs(int x){ if(mem[x]) return mem[x]; //如果已经有值 用现成的 int sum=0; if(x==1) sum=1; else if(x==2) sum=2; else sum=dfs(x-1)+dfs(x-2); mem[x]=sum; return sum;}int main(){ cin>>n; int res=dfs(n); cout<<res<<endl; ...
细节化の宽搜BFS2.0
小进阶关于memset它是按照字节对内存块初始化 对于int数组 只能初始化为0或-1 否则不稳定其它情况还是for来初始化比较妥当初始化一个0x3f 可以当无穷大使用
因为调用库会有点慢 所以应学会数组模拟队列快速复习一下int q[N],hh=0,tt=-1; //hh队头 tt队尾 头在左边便于数组操作//插入q[++tt]=x;//弹出hh++; 队头指针直接右移一个位置//判断是否为空if(hh<=tt) not emptyelse empty
bfs中队列的两个性质1.队列里最多存在两种状态 当取出队头 队尾就会新增x+12.单调性 前一段状态为x 后一段状态为x+1
双端队列由bfs队列中性质 若是走白给的点 那么就把这个点插到队头继续搜如果是要费用的点 插到队尾 这样就保证了单调性
[洛谷4554] [c++]123456789101112131415161718192021222324252627282930313233343536373839 ...
细节化の宽搜BFS
BFS主要解决两类问题1.从a出发是否存在到达b的路径2.从a出发到b的最短路径数据20以内dfs可能行。。。推荐bfs大概就是对于一个点 一层一层访问周围的点（类似于子节点的子节点）整体思路：起始 扩散 终止
需要队列的原因：需要一层一层遍历 相邻节点的访问顺序需要确定即使得先遍历到的节点先被存储 再按照存储先后顺序取出来遍历其子节点 综上所述队列符合
两道热身题
[洛谷1716离开中山路] [c++]123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>using namespace std;const int N=1010;int g[N][N]; //存地图int dist[N][N];typedef pair<int,int> PII;queue<PII> s;int n,x1,y11,x2,y2=0;int dx[]={1,0,-1,0 ...