zzqwtc

分类

题解(3)

/ 注册

全部文章（共57篇）

邻接表

邻接表的数组实现 #include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n...

2021-01-25

0 418

最小生成树之Prim算法

#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using namespace ...

2021-01-25

0 516

最小生成树之Kruskal算法

具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止。把所有边按权值从小到大排序遍历每条边如果这条边的两个顶点一个在树内一个在树外则将顶点入树保证了每条边的权值都是最小的最终得到的树即为最小生成树...

2021-01-25

0 486

最小生成树之Prim算法+堆优化

#include<bits/stdc++.h> #define INF 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define endl '\n' using n...

2021-01-25

0 614

最短路之Floyd算法

Floyd算法不能判断负环算法思路判断是否可以通过中转点 k 使 i 到 j 的距离减小如图设i-j为100 i-k为40 k-j为40 显然通过k的中转从i到j所耗费的路程变短了 #include<bits/stdc++.h> #define INF 0x3f3f3f3f...

2021-01-25

0 513

最短路之Dijkstra+堆优化（单源最短路）

优先队列实现对Dijkstra的优化求单源最短路 #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false) #define...

2021-01-25

0 521

Bellman-Ford

Bellman-Ford算法用于求单源最短路包含负权边的问题，还可以检测图中是否有负环 #include<bits/stdc++.h> #define INF 0x3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_st...

2021-01-25

0 434

SPFA(队列优化的Bellman-Ford算法)

SPFA（Shortest path faster algorithm）算法思想基于Bellman-Ford算法进行优化的方式是在进行某一次松弛操作中如果起点到一个点的距离不变那么以这个点为中转点能到达的点距起点的距离不变如果这个点的距离发生了变化就将这个点入队列以求通过这个点中转...

2021-01-25

0 653

LCS（最长公共子序列）

给出两个字符串求其最长公共子序列 #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<map> #include<cs...

2021-01-25

0 411

LIS(最长递增子序列)

算法：动态规划＋二分查找时间复杂度：O(nlogn) #include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<map> #inc...

2021-01-25

0 558