搜索与图论
搜索
dfs
用栈实现
1_排列数字
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
bool st[N];
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; ++ i) printf("%d ", path[i]);
puts("");
return;
}
for (int i = 1; i <= n; ++ i)
if (!st[i]) {
path[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false;
}
}
int main() {
scanf("%d", &n);
dfs(0);
return 0;
}
2_n皇后问题
第一种搜索顺序
#include <iostream>
using namespace std;
const int N = 20;
char g[N][N];
int n;
bool col[N], dg[N], udg[N];
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; ++ i) puts(g[i]);
puts("");
return;
}
for (int i = 0; i < n; ++ i)
if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[n - u + i] = false;
g[u][i] = '.';
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
g[i][j] = '.';
dfs(0);
return 0;
}
第二种搜索顺序(更原始)
#include <iostream>
using namespace std;
const int N = 20;
char g[N][N];
int n;
bool col[N], dg[N], udg[N], row[N];
void dfs(int x, int y, int s) {
if (y == n) y = 0, x ++;
if (x == n) {
if (s == n) {
for (int i = 0; i < n; ++ i) puts(g[i]);
puts("");
}
return;
}
dfs(x, y + 1, s);
if (!col[y] && !row[x] && !dg[x + y] && !udg[x - y + n]) {
g[x][y] = 'Q';
col[y] = row[x] = dg[x + y] = udg[x - y + n] = true;
dfs(x, y + 1, s + 1);
col[y] = row[x] = dg[x + y] = udg[x - y + n] = false;
g[x][y] = '.';
}
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
g[i][j] = '.';
dfs(0, 0, 0);
return 0;
}
bfs
用队列实现
1走迷宫
#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m, d[N][N], g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
PII q[N * N], Prev[N][N]; // Prev 数组记录路径
int dfs() {
int tt = 0, hh = 0;
q[0] = {0, 0};
memset(d, -1, sizeof d);
d[0][0] = 0;
while (hh <= tt) {
PII t = q[hh ++];
for (int i = 0; i < 4; ++ i) {
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && y >= 0 && x < n && y < m && g[x][y] == 0 && d[x][y] == -1) {
d[x][y] = d[t.first][t.second] + 1;
Prev[x][y] = t;
q[++ tt] = {x, y};
}
}
}
int x = n - 1, y = m - 1; // 输出路径（逆）
while (x || y) {
cout << x << ' ' << y << endl;
PII t = Prev[x][y];
x = t.first, y = t.second;
}
return d[n - 1][m - 1];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < m; ++ j)
cin >> g[i][j];
cout << dfs() << endl;
return 0;
}
图
有向图和无向图
无向图 ： 边没有方向的图称为无向图。
有向图 : 边有方向
存图
邻接表
int h[N], e[M], ne[M], idx;
void add(int a, int b) { // 加边
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
图的深度优先搜索
图的宽度优先搜索
// 宽搜框架
queue <- 1
while queue 不空 {
t <- 队头
拓展t的所有零点x
if (x未遍历) {
queue <- x // x 入队
d[x] = d[t] + 1
}
}
拓扑排序
有向图才有拓扑序列（有向无环图又叫拓扑图）
性质：一个有向无环图一定至少存在一个入度为0的点
度数
入度 : 有向图中某点作为图中边的终点的次数之和
出度 : 顶点的出边条数称为该顶点的出度
queue <- 所有入度为0的点 // 入度为0的点就是起点
while queue 不空 {
t <- 队头
枚举t的所有出边 t -> j
删掉 t -> j , d[j] --
if (d[j] == 0) {
queue <- j
}
}
最短路
n：定点数；m：边数
单源最短路
所有边权都是正数
朴素Dijkstra算法
O(n^2) (m, n <= 1e5；即稠密图)
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int n, m, a, b, c;
int g[N][N]; // 稠密图用邻接矩阵存
int dist[N]; // 距离起点的距离
bool st[N]; // 该点距离有无确定
int dijkstra() {
memset(dist, 0x3f, sizeof dist); // 所有点的距离初始化为+∞
dist[1] = 0;
for (int i = 0; i < n - 1; ++ i) {
int t = -1;
// 在所有没有确定最短距离的点中找到最近的点t
for (int j = 1; j <= n; ++ j)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t点更新其他点的最短路
for (int j = 1; j <= n; ++ j)
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m --) {
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c);
// 重边取最小即可
}
printf("%d\n", dijkstra());
return 0;
}
堆优化的Dijkstra算法
O(mlogn) (m,n > 1e5；即稀疏图)
// 堆优化dijkstra算法 --- 稀疏图
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m, a, b, c;
int h[N], w[N], e[N], ne[N], idx; // 稀疏图用邻接表存
int dist[N];
bool st[N];
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;
priority_queue<PII, vector<PII>, greater<PII>> heap;
// 定义小根堆 first---距离 second---点的编号
heap.push({0, 1});
while (heap.size()) {
// 每次取出距离最短的点
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
// 如果ver点的最短路已经确定那么continue
if (st[ver]) continue;
st[ver] = true;
// 更新ver点连的边的最短路
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[ver] + w[i]) {
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m --) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
// 邻接表不用考虑重边
}
printf("%d\n", dijkstra());
return 0;
}
存在负权边
Bellman-Ford
O(nm)
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510, M = 1e4 + 10;
struct Edge {
int a, b, c;
} edge[M];
int n, m, k, a, b, c;
int dist[N];
int last[N]; // 上次的最短路
void bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; ++ i) { // 走k次
memcpy(last, dist, sizeof dist); // 防止出现串联
for (int j = 0; j < m; j ++) {
auto e = edge[j];
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
// 松弛操作
} // 三角不等式---dist[b]<=dist[a]+c
}
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; ++ i) {
scanf("%d%d%d", &a, &b, &c);
edge[i] = {a, b, c};
}
bellman_ford();
// 因为存在负权边可能存在dist[x]==INF-y(y比较小)
// 所有只要判断>一个比较大的数即可
if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else printf("%d\n", dist[n]);
return 0;
}
SPFA
一般：O(m)；最坏：O(nm)
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
int n, m, a, b, c;
int h[N], e[N], ne[N], idx, w[N];
int dist[N];
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, w[idx] = c, ne[idx] = h[a], 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()) {
int 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;
}
}
}
}
return dist[n];
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m --) {
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
int t = spfa();
if (t == 0x3f3f3f3f) puts("impossible");
else printf("%d\n", t);
return 0;
}
多源汇最短路
Floyd算法
O(n^3)
源点即起点
汇点即终点
#include <iostream>
#include <cstring>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int d[N][N];
int a, b, c;
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] = min(d[i][j], d[i][k] + d[k][j]);
}
int main() {
scanf("%d%d%d", &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 --) {
scanf("%d%d%d", &a, &b, &c);
d[a][b] = min(d[a][b], c);
}
floyd();
while (Q --) {
scanf("%d%d", &a, &b);
int t = d[a][b];
if (t > INF / 2) puts("impossible");
else printf("%d\n", t);
}
return 0;
}
最小生成树
Prim
朴素版Prim
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N]; // 表示一个点是否在集合里
int a, b, c;
int prim() {
memset(dist, 0x3f, sizeof dist);
// 初始化成+∞
int res = 0;
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;
// 如果不能到达集合说明不存在最小生成树
if (i && dist[t] == INF) return INF;
// 此句写在31行前避免自环
if (i) res += dist[t];
st[t] = true; // 将t加入集合
// 用t更新其他点到集合的距离
for (int j = 1; j <= n; ++ j) dist[j] = min(dist[j], g[t][j]);
}
return res;
}
int main() {
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while (m --) {
scanf("%d%d%d", &a, &b, &c);
g[a][b] = g[b][a] = min(g[a][b], c);
}
int t = prim();
if (t == INF) puts("impossible");
else printf("%d\n", t);
}
O(n^2)
堆优化Prim
O(mlogn)
// 基本上用不到
// 就不写了
Kruskal
O(mlogm)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10, M = 2e6 + 10, INF = 0x3f3f3f3f;
int n, m;
int p[N]; // 并查集数组
struct Edge {
int a, b, w;
bool operator < (const Edge &W) const {
return w < W.w;
} // 运算符重载，写了可以不用写cmp
} edges[M];
int find(int x) {
return p[x] == x ? p[x] : p[x] = find(p[x]);
}
int kruskal() {
sort(edges, edges + m);
// 将所有点按权重从小到大排序 O(mlogm)
// 排序算法常数小
// 所以能跑的比较快
for (int i = 1; i <= n; ++ i) p[i] = i;
// 初始化并查集
int res = 0, cnt = 0;
// res表示生成树中所有边权之和
// cnt表示加入了多少边
for (int i = 0; i < m; ++ i) {
// 枚举每条边
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
// 如果a，b不连通
a = find(a), b = find(b);
if (a != b) {
p[a] = b; // 将这条边加入集合中
res += w;
cnt ++;
}
}
// 如果有边未加入集合说明最小生成树不存在
if (cnt < n - 1) return INF;
return res;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 0; i < m; ++ i) {
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
int t = kruskal();
if (t == INF) puts("impossible");
else printf("%d\n", t);
}
二分图
二分图：节点由两个集合组成，且两个集合内部没有边的图
性质：一个图是二分图当且仅当图中不含奇数环
染色法
O(n+m)
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10, M = 2e6 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
int a, b;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool dfs(int u, int c) {
color[u] = c;
// 将u染成c颜色
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!color[j]) { // 如果没有染色就染色
if (!dfs(j, 3 - c)) return false; // 1->2, 2->1
} // 相邻两点颜色不能相同
else if (color[j] == c) return false;
}
return true;
}
int main() {
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m --) {
scanf("%d%d", &a, &b);
add(a, b), add(b, a); // 无向图
}
bool flag = true;
// 遍历所有点，如果i未染色，将其所在的连通块染色
// 如果一个点染色，那么这个点所在的连通块的颜色就已确定
for (int i = 1; i <= n && flag; ++ i)
if (!color[i] && !dfs(i, 1)) flag = false; // 如果产生矛盾则不是二分图
puts(flag ? "Yes" : "No");
}
匈牙利算法
O(mn), 实际运行时间一般远小于O(mn) [可能是线性的也说不定]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
// y总的奇妙比喻（男生表示左边点，女生表示右边点）
const int N = 510, M = 1e6 + 10;
int n1, n2, m;
int h[N], e[M], ne[M], idx; // 数组越界可能发生任何错误，不只是段错误
int match[N]; // 记录每个女生配对的男生
bool st[N]; // 记录每个女生有没有遍历过
int a, b;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool find(int x) {
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true;
if (match[j] == 0 || find(match[j])) { // 如果女生没有配对或能匹配别的男生则匹配
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
scanf("%d%d%d", &n1, &n2, &m);
memset(h, -1, sizeof h);
while (m --) {
scanf("%d%d", &a, &b);
add(a, b); // 存男生指向女生即可
}
int res = 0;
for (int i = 1; i <= n1; ++ i) {
memset(st, false, sizeof st);
if (find(i)) res ++;
}
printf("%d\n", res);
}
