1，DFS
深度优先搜索，代表题目有全排列、n皇后等。
DFS常见题目
2，BFS
1）初始化队列q
2）当队列不为空，取出队头元素，扩展队头
while (q不为空)
{
t = q.front();
q.pop();
扩展t
}
3，树与图的存储
树是一种特殊的图，与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。
(1) 邻接矩阵：g[a][b] 存储边a->b
(2) 邻接表：
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);
4，树与图的遍历
时间复杂度 O(n+m)，n 表示点数，m 表示边数
(1) 深度优先遍历
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
(2) 宽度优先遍历
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true; // 表示点j已经被遍历过
q.push(j);
}
}
}
5，拓扑排序
时间复杂度 O(n+m)，n 表示点数，m 表示边数
/*
有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列
1,一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。
2,一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
//h[i]. e[i], ne[i], idx创建邻接表，d[i]表示下标为i的点的入度（有多少条边指向i）
int h[N], e[N], ne[N], idx, d[N];
int n, m;
//q是宽搜所用的队列，res记录符合入度为0的点
queue<int> q;
vector<int> res;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool topsort() {
//将入度为0的点入队
for (int i = 1; i <= n; i++)
if (!d[i])
q.push(i);
while (q.size()) {
auto t = q.front();
q.pop();
//记录队里的元素
res.push_back(t);
//遍历t的所有边
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
//如果删去t指向j的边，如果此时j的入度为0，就入队
if (--d[j] == 0)
q.push(j);
}
}
//如果n个点都可以变为入度为0，说明是拓扑图
return res.size() == n;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;
}
if (topsort()) {
for (auto x : res) cout << x << " ";
cout << endl;
}
else puts("-1");
return 0;
}
6，最短路
最短路求解方法
6.1 朴素dijkstra算法
时间复杂是 O(n2+m)，n 表示点数，m 表示边数
/*
朴素dijkstra：
1，初始化距离数组dist[1] = 0, dist[i] = 0x3f;
st：当前已经确定最短距离的点
2，迭代n次
1) 找到当前未在st中标记过且离起点最近的点t
2) 将该点t进行标记
3) 用t更新其他点的距离
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
//g[i][j]邻接矩阵，因为是稠密图，所以需要用邻接矩阵存储，表示从i到j的权值
//dist[i]表示下标为i的点到第一个点的距离
int g[N][N], dist[N];
//st[i]表示下标为i的点的距离是否确定
bool st[N];
int n, m;
int dijsktra() {
//初始化距离为正无穷
memset(dist, 0x3f, sizeof dist);
//第一个点到本身的距离为0
dist[1] = 0;
//迭代n次
for (int i = 0; i < n; i++) {
//
int t = -1;
//遍历dist数组，找到没有确定最短路径的节点中距离起点最近的点t
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
//确定t后更新状态
st[t] = true;
//用最小的点t去更新其他的点到起点的距离
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
//如果起点到达不了n号节点，则返回-1
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
//初始化图
memset(g, 0x3f, sizeof g);
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
//如果发生重边就只需要保留最短的一条边
g[a][b] = min(g[a][b], c);
}
cout << dijsktra() << endl;
return 0;
}
6.2，堆优化版dijkstra
时间复杂度 O(mlogn)，n 表示点数，m 表示边数
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010;
int h[N], e[N], ne[N], w[N], idx, dist[N];
bool st[N];
int n, m;
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
//heap是小根堆
priority_queue<PII, vector<PII>, greater<PII>> heap;
//将下标为1的点插入小根堆，first表示距离，second表示下标
heap.push({0, 1});
while (heap.size()) {
//取不在集合st中距离最短的点，因为小根堆已经排序，所以只需要取堆顶元素
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
//如果t被访问过，就continue
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
///如果j到1的距离大于ver到1的距离加上ver到j的距离，就更新值的大小；
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
//更新距离之后将该点的距离加入到堆中
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}
6.3，Bellman-Ford算法
时间复杂度 O(nm)，n 表示点数，m 表示边数
/*
bellman_ford算法：
1，循环k次
2，遍历所有的边
3，更新距离数组
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 10010;
int dist[N], backup[N];
int n, m, k;
struct Edge{
int a, b, w;
}edge[M];
int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i++) {
//这里需要备份，防止影响到下一个点
memcpy(backup, dist, sizeof dist);
for (int j = 0; j < m; j++) {
int a = edge[j].a, b = edge[j].b, w = edge[j].w;
dist[b] = min(dist[b], backup[a] + w);
}
}
/*
这里不是等于0x3f3f3f3f是因为0x3f3f3f3f是一个确定的值，会受到其他数值影响，
只要判断和0x3f3f3f3f一个量级即可。
返回0x3f3f3f3f是因为如果返回-1，可能导致与正确答案冲突
*/
if (dist[n] > 0x3f3f3f3f / 2) return 0x3f3f3f3f;
return dist[n];
}
int main() {
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
edge[i] = {a, b, w};
}
int res = bellman_ford();
if (res == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << res << endl;
return 0;
}
6.4，spfa 算法（队列优化的Bellman-Ford算法）
时间复杂度 平均情况下 O(m)，最坏情况下 O(nm)，n 表示点数，m 表示边数
/*
spfa算法：
1，建立一个队列，初始时队列里只有起始点
2，再建立一个数组记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）
3，再建立一个数组，标记点是否在队列中
4，队头不断出队，计算始点起点经过队头到其他点的距离是否变短，如果变短且被点不在队列中，则把该点加入到队尾
5，重复执行直到队列为空
6，在保存最短路径的数组中，就得到了最短路径
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], w[N], idx, dist[N];
bool st[N];
int n, m;
void add(int a, int b, int c) {
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
int spfa() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
//标记点已经在队列中
st[1] = true;
while (q.size()) {
auto t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
//如果始点起点经过队头到其他点的距离变短
if (dist[j] > dist[t] + w[i]) {
//更新距离
dist[j] = dist[t] + w[i];
//如果该点不在队列，加入队列
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return 0x3f3f3f3f;
return dist[n];
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int res = spfa();
if (res == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << res << endl;
return 0;
}
6.5，floyd算法
时间复杂度是 O(n3)，n 表示点数
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
//邻接矩阵，d[i][j]表示i到j的最短距离
int d[N][N];
int n, m, q;
int INF = 1e9;
void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
//更新d[i][j]的最短距离
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
/*动态规划的思想*/
int main() {
cin >> n >> m >> q;
//初始化距离
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
d[a][b] = min(d[a][b], c);
}
floyd();
while (q--) {
int x, y;
cin >> x >> y;
int res = d[x][y];
if (res > INF / 2) cout << "impossible" << endl;
else cout << d[x][y] << endl;
}
return 0;
}
7，最小生成树
最小生成树求解方法
7.1，朴素版prim算法
时间复杂度是 O(n2+m)，n 表示点数，m 表示边数
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
//g[i][j]存储图
int g[N][N];
//dist[i]表示i到生成树的距离
int dist[N];
//st[i]表示i是否加入到生成树
bool st[N];
int prim() {
memset(dist, 0x3f, sizeof dist);
int res = 0;
//循环n次
for (int i = 0; i < n; i++) {
int t = -1;
//找到没有在生成树中并且离生成树距离最短的点
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
//如果这个点是孤立点，返回INF
if (i && dist[t] == INF) return INF;
//否则加入答案
if (i) res += dist[t];
//标记已经加到生成树
st[t] = true;
//更新到集合的距离（与dijkstra不同）
for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if (t == INF) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
7.2，Kruskal算法
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
int p[N];
int n, m;
struct Edge {
int a, b, w;
//重载小于号
bool operator < (const Edge& W) {
return w < W.w;
}
}e[N];
//并查集找x的祖先节点
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int Kruskal() {
//根据权值对边进行从小到大排序
sort(e, e + m);
//初始化并查集
for (int i = 1; i <= n; i++) p[i] = i;
//res记录最小生成树权重之和，cnt记录生成树的边数量
int res = 0, cnt = 0;
//遍历所有边
for (int i = 0; i < m; i++) {
int a = e[i].a, b = e[i].b, w = e[i].w;
a = find(a), b = find(b);
//如果a，b不在一个集合，就加入到集合中，res增加ab边的权值，cnt增加一条边
if (a != b) {
res += w;
cnt++;
p[a] = b;
}
}
//n个节点有n-1条边，如果小于n-1说明不能生成树
if (cnt < n - 1) return INF;
return res;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
e[i] = {u, v, w};
}
int t = Kruskal();
if (t == INF) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
8，二分图
二分图求解方法
8.1，染色法判别二分图
时间复杂度是 O(n+m)，n 表示点数，m 表示边数
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int color[N], h[N], e[N], ne[N], idx;
int n, m;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//把节点u染色成v
bool dfs(int u, int v) {
color[u] = v;
//遍历与u相连的边
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
//如果这个点没有染色
if (!color[j]) {
//进行染色，如果染色不成功，不是二分图
if (!dfs(j, 3 - v)) return false;
}
//如果这个点已经染色，但是颜色不是相反的颜色，冲突
else if (color[j] && color[j] != 3 - v)
return false;
}
return true;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
//遍历每一个点
for (int i = 1; i <= n; i++) {
//如果这个点没有染色
if (!color[i]) {
//进行染色，如果染色不成功，不是二分图
if (!dfs(i, 1)) {
cout << "No" << endl;
return 0;
}
}
}
//如果染色成功，是二分图
cout << "Yes" << endl;
return 0;
}
8.2，匈牙利算法
#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e5 + 10;
int h[N], e[M], ne[M], idx;
//match[i] = j 表示i的男朋友是j
int match[N];
//st[i] = true表示i已经有男生在追了
bool st[N];
int n1, n2, m;
int add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool find(int x) {
//遍历所有x喜欢的女生
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
//如果j没有男朋友
if (!st[j]) {
//男生开始追j
st[j] = true;
//如果j没有男朋友或者可以给j的男朋友找到另一个女生
if (match[j] == 0 || find(match[j])) {
//x就可以做j的男朋友
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
cin >> n1 >> n2 >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
//为男生依次找女朋友
for (int i = 1; i <= n1; i++) {
//因为每一轮男生一开始都没有追女生，所以每次st都为false
memset(st, false, sizeof st);
//如果找到了，res++
if (find(i)) res++;
}
cout << res << endl;
return 0;
}
