- 搜索类
- 图类
- 排序类
- 并查集
- 数学类
- 位运算
Part1 搜索类
-
bfs 求迷宫问题最短路径（未验证）
#include<iostream>
#include<queue>
using namespace std;
//用于遍历的结构 (可以添加题目所要求的信息)
typedef struct Node{
int x,y;
int step;
}NODE;
const int NUM = 100; //地图最大范围，根据要求具体修改
int M,N;
int m[NUM][NUM]; // 地图数组
int vis[NUM][NUM];
bool check(NODE& node){
int x = node.x;
int y = node.y;
//三种不可访问情况
if(x < 1 || y < 1 || x > M || y > N ) return 0; //地图边界判断（一定要最先判断）
if(vis[x][y]) return 0; //是否被访问过判断
if(m[x][y] == '*') return 0; //是否是不可访问的节点判断（具体题目不同 假设为*)
//可访问
return 1;
}
//判断是否是所求的节点
bool checkRight(NODE& node){
if(m[node.x][node.y] == '1') return 1; //假设1为目标
return 0;
}
int mov[4][2]={{0,1},{0,-1},
{1,0},{-1,0}}; //用于移动的数组，这里是四个方向（具体问题具体分析）
NODE bfs(NODE startNode){
//初始化
queue<NODE> Q;
vis[startNode.x][startNode.y] = 1;
Q.push(startNode);
//正式开始遍历
while(!Q.empty()){
NODE nowNode = Q.front(); //获取判断节点
if(checkRight(nowNode)) return nowNode; //达到目标节点，获取目标节点
//进行四个方向遍历(具体问题可能会不同)
for(int i = 0; i < 4; i++){
NODE nextNode;
//下一个位置信息
nextNode.step = nowNode.step + 1;
nextNode.x = nowNode.x + mov[i][0];
nextNode.y = nowNode.y + mov[i][1];
if(check(nextNode)){ //判断是否可访问;
vis[nextNode.x][nextNode.y] = 1; //标记为已访问
Q.push(nextNode);
}
}
}
}
int main(){
cin >> M >> N;
for(int i = 1; i <= M; i++)
for(int j = 1; j <= N; j++)
cin >> m[i][j];
//初始节点(根据题目具体要求位置)
NODE sNode;
sNode.step = 0;
sNode.x = 1;
sNode.y = 1;
NODE targetNode = bfs(sNode);
cout << targetNode.step << endl; //输出题目要的节点信息
}
-
dfs
求总的路径数目
Part2 图类
-
最小生成树 （Prim）
#include<iostream>
using namespace std;
const int INF = 0x3fffffff;
int vis[N];
void prim(int c[][],int u) {
int i,j;
vis[u] = 1;
for(i = 1; i <= N; i++) {
closet[i] = c[u][i];
}
for(i = 0; i < N; i++){
int t = u;
int min = INF;
int j;
for(j = 1; j <= N; j++){
if(!vis[u] && lowcost[j] < min){
min = closet[j];
t = j;
}
}
if (t == u) break;
for(j = 1; j <= N; j++){
if(!vis[j] && lowcost[j]>c[t][j]){
lowcost[j] = c[t][j];
}
}
}
}
-
单元最短路 （DJ）
const int MAXINT = 32767;
const int MAXNUM = 10;
int dist[MAXNUM];
int prev[MAXNUM];
int A[MAXUNM][MAXNUM];
void Dijkstra(int v0)
{
bool S[MAXNUM]; // 判断是否已存入该点到S集合中
int n=MAXNUM;
for(int i=1; i<=n; ++i)
{
dist[i] = A[v0][i];
S[i] = false; // 初始都未用过该点
if(dist[i] == MAXINT)
prev[i] = -1;
else
prev[i] = v0;
}
dist[v0] = 0;
S[v0] = true;
for(int i=2; i<=n; i++)
{
int mindist = MAXINT;
int u = v0; // 找出当前未使用的点j的dist[j]最小值
for(int j=1; j<=n; ++j)
if((!S[j]) && dist[j]<mindist)
{
u = j; // u保存当前邻接点中距离最小的点的号码
mindist = dist[j];
}
S[u] = true;
for(int j=1; j<=n; j++)
if((!S[j]) && A[u][j]<MAXINT)
{
if(dist[u] + A[u][j] < dist[j]) //在通过新加入的u点路径找到离v0点更短的路径
{
dist[j] = dist[u] + A[u][j]; //更新dist
prev[j] = u; //记录前驱顶点
}
}
}
}
-
多源最短路 （Floyd）
typedef struct
{
char vertex[VertexNum]; //顶点表
int edges[VertexNum][VertexNum]; //邻接矩阵,可看做边表
int n,e; //图中当前的顶点数和边数
}MGraph;
void Floyd(MGraph g)
{
int A[MAXV][MAXV];
int path[MAXV][MAXV];
int i,j,k,n=g.n;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
A[i][j]=g.edges[i][j];
path[i][j]=-1;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(A[i][j]>(A[i][k]+A[k][j]))
{ A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
} }
Part3 排序类
-
数组排序 sort
可对任意类型的数组排序。可以自定义排序规则
#include<algorithm> //头文件
sort(数组名,数组名+数组长度) //自定义排序
sort(数组名,数组名+数组长度,cmp比较规则) //自定义排序
//自定义排序规则
bool cmp(Node& a , Node& b){
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
- cmp排序函数的自定义方法：
return true 就是a在b前
return false 就是b在a前 - 默认排序例子（小到大）
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5;
int main(){
int arr[N];
for(int i = 0; i < 5; i++){
cin >> arr[i];
}
sort(arr, arr + N);
for(int i = 0; i < 5; i++){
cout << arr[i] <<endl;
}
return 0;
}
- 自定义排序例子
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct NODE{
int x,y;
}Node;
//自定义排序规则
bool cmp(Node& a , Node& b){
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
const int N = 5;
int main(){
Node arr[N];
for(int i = 0; i < 5; i++){
cin >> arr[i].x >> arr[i].y;
}
sort(arr, arr + N, cmp); //自定义排序
for(int i = 0; i < 5; i++){
cout << arr[i].x << " " <<arr[i].y <<endl;
}
return 0;
}
-
优先队列 priority_queue
用于动态排序的结构（需要不断的改变排序的元素）
如：哈夫曼树的构造
#include<queue>
priotrity_queue<ElemType> pq //默认定义 从大到小
priotrity_queue<ElemType, vector<ElemType>,cmp > pq
//自定义排序规则 （有两种不用自己写的规则less<int>和greater<int> less和默认一样从大到小 greater从小到大）
struct cmp {
bool operator() (Node& a , Node& b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
};
//基本方法
pq.push(node) //加入队列
pq.empty() //队列是否
pq.top() //获得队头元素（注意和queue的区别，queue是front）
pq.pop() //出队
注意：true false 对应的方向刚好与sort相反
- 初步使用
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 5;
int main(){
priority_queue<int, vector<int>, greater<int> > pq; //整型从小到大
// priority_queue<int, vector<int>, less<int> > pq; //整型从大到小 同priority_queue<int> pq;
int x;
for(int i = 0; i < 5; i++){
cin >> x;
pq.push(x);
}
while(!pq.empty()){
cout << pq.top() <<endl;
pq.pop();
}
return 0;
}
- 自定义排序例子
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define Node ElemType
using namespace std;
const int N = 5;
typedef struct NODE{
int x,y;
}Node;
//自定义排序规则
struct cmp {
bool operator() (Node& a , Node& b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
};
int main(){
Node arr[N];
priority_queue<Node, vector<Node>, cmp> pq;
for(int i = 0; i < 5; i++){
cin >> arr[i].x >> arr[i].y;
pq.push(arr[i]);
}
while(!pq.empty()){
cout << pq.top().x << " " << pq.top().y <<endl;
pq.pop();
}
return 0;
}
Part4 并查集
初始化数组为-1
find(int a); //找老大
union(int a, int b) // a集团加入b集团
不带路径压缩：
int find(int a){
return boss[a]?find(a):a;
}
void union(int a, int b){
int fa = find(a);
int fb = find(b);
boss[a] = b;
}
带路径压缩：
int find(int a){
int bigBoss;
int son = a;
int temp;
while(boss[a]) a = boss[a];
bigBoss = a; //找到大老板
//把路径上的上司不是大老板的全部直属大老板
while( son != bigBoss ){
temp = boss[son];
boss[son] = bigBoss;
son = temp;
}
return bigBoss;
}
void union(int a, int b){
int fa = find(a);
int fb = find(b);
boss[a] = b;
}
Part5 数学类
- 最大公因数（辗转相除法）
int gcd(int a, int b){
return b>0?gcd(b,a%b):a;
}
- 最小公倍数
int gcd(int a, int b){
return b>0?gcd(b,a%b):a;
}
int lcm(int a, int b){
return a*b/gcd(a,b);
}
网友评论