模版(全排列)
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
void dfs(int u, int state) {
// 终止条件：达到n个数
if (u == n) {
for (int i = 0; i < n; i++) cout << path[i] << " ";
cout << endl;
return;
}
for (int i = 0; i < n; i++) {
// 状态压缩，若该位没有走过则递归
if (!(state >> i & 1)) {
path[u] = i + 1;
dfs(u + 1, state + (1 << i));
}
}
}
int main() {
cin >> n;
dfs(0, 0);
return 0;
}
n皇后
#include <iostream>
using namespace std;
const int N = 10;
int n;
char g[N][N];
bool c[N], r[N], dg[N * 2], udg[N * 2];
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++) {
for (int j = 0; j < n; j++)
cout << g[i][j];
cout << endl;
}
cout << endl;
}
return;
}
// 先尝试不填(*)
g[x][y] = '.';
dfs(x, y + 1, s);
// 若条件允许，填入皇后
if (!r[x] && !c[y] && !dg[x + y] && !udg[x - y + n]) {
g[x][y] = 'Q';
// 注意对对角线和反对角线的处理
r[x] = c[y] = dg[x + y] = udg[x - y + n] = true;
dfs(x, y + 1, s + 1);
r[x] = c[y] = dg[x + y] = udg[x - y + n] = false;
}
}
int main() {
cin >> n;
dfs(0, 0, 0);
return 0;
}
模版
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
int g[N][N], d[N][N];
int bfs() {
queue<PII> q;
// 可能距离为0，故为避免冲突初始化为-1作为判据
memset(d, -1, sizeof d);
d[0][0] = 0;
q.push({ 0,0 });
int dx[] = { -1,0,0,1 };
int dy[] = { 0,-1,1,0 };
// 碰到bfs就要想到维护队列
while (q.size()) {
auto t = q.front();
q.pop();
int x = t.first, y = t.second;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 0 && d[nx][ny] == -1) {
d[nx][ny] = d[x][y] + 1;
q.push({ nx,ny });
}
}
}
// 下标是0-indexed,所以是d[n-1][m-1]
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 << bfs() << endl;
return 0;
}
八数码
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
using namespace std;
int bfs(string state) {
// 将八个数字和x用字符串储存，作为广义坐标，再利用哈希表将其与跟当前(出发点)的距离对应
queue<string> q;
unordered_map<string, int> d;
// 注意是d[state]=0, 而不是d[end]=0
d[state] = 0;
q.push(state);
string end = "12345678x";
while (q.size()) {
auto t = q.front();
q.pop();
int distance = d[t];
if (t == end) return distance;
int dx[] = { -1,0,0,1 };
int dy[] = { 0,-1,1,0 };
int k = t.find('x');
int a = k / 3, b = k % 3;
for (int i = 0; i < 4; i++) {
int x = a + dx[i], y = b + dy[i];
if (x >= 0 && x < 3 && y >= 0 && y < 3) {
swap(t[k], t[x * 3 + y]);
if (!d[t]) {
d[t] = distance + 1;
q.push(t);
}
swap(t[k], t[x * 3 + y]);
}
}
}
return -1;
}
int main() {
char s[2];
string state;
for (int i = 0; i < 9; i++) {
cin >> s;
state += *s;
}
cout << bfs(state) << endl;
return 0;
}
树的重心
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int n, ans = N;
int h[N], e[M], ne[M], idx;
bool st[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int u) {
st[u] = true;
int size = 0, sum = 0;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (st[j]) continue;
//将每一个子节点深入到叶节点，返回该分支的总数
int s = dfs(j);
sum += s;
//更新最大值
size = max(size, s);
}
// 取本节点和本节点之上所有联通的节点
size = max(size, n - sum - 1);
ans = min(size, ans);
// 返回当前节点及以下形成的树的大小(注意还有其本身，故需要+1)
return sum + 1;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}
图中点的层次
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx, d[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs() {
queue<int> q;
memset(d, -1, sizeof d);
d[1] = 0;
q.push(1);
while (q.size()) {
auto t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1) {
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
有向图的拓扑序列
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int n, m;
int h[N], e[M], ne[M], idx;
// 手动模拟队列
int q[N], d[N];
// 邻接表存图
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
bool topsort() {
int hh = 0, tt = -1;
// 先将所有
for (int i = 1; i <= n; i++) {
if (!d[i]) q[++tt] = i;
}
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
// 从队列中取出一点，其所有临近点入度减一
if (--d[j] == 0) {
// 若删去该点后入度为0，可入队(注意是++tt的顺序)
q[++tt] = j;
}
}
}
return tt == n - 1;
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b;
cin >> a >> b;
add(a, b);
// 注意加边后b的入度加一
d[b]++;
}
if (!topsort()) cout << -1 << endl;
else {
for (int i = 0; i < n; i++) cout << q[i] << " ";
cout << endl;
}
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
int n, m;
int dist[N], g[N][N];
bool st[N];
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 1; i < n; i++) {
// 先调出目前距离起点最短者
int u = -1;
for (int j = 1; j <= n; j++) {
if (!st[j] && (u == -1 || dist[j] < dist[u]))
u = j;
}
// 注意标记该点已确定最短距离
st[u] = true;
// 用该点更新其他点到初始点的距离
for (int j = 1; j <= n; j++) {
if (dist[j] > dist[u] + g[u][j])
dist[j] = dist[u] + g[u][j];
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main() {
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m--) {
int a, b, d;
cin >> a >> b >> d;
g[a][b] = min(g[a][b], d);
}
cout << dijkstra() << endl;
return 0;
}
堆优化版(稀疏图)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 1000010;
int n, m;
int dist[N];
int h[N], e[N], ne[N], w[N], idx;
bool st[N];
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
用heap<pair>存点的序号和距离，注意距离在前，以便排序
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({ 0,1 });
while (heap.size()) {
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
// 更新了距离的点入队，为更新其他点准备
heap.push({ dist[j],j });
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
else 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;
}
模版(限制经过的边数时必须用这个)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510, M = 100010;
int n, m, k;
int dist[N], last[N];
// 所有边暴力遍历，故直接用结构体来存放
struct Edge
{
int a, b, c;
}edges[M];
void bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i++) {
// 必须用last数组存上轮的数据，防止被污染
memcpy(last, dist, sizeof dist);
for (int j = 1; j <= m; j++) {
auto e = edges[j];
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
}
}
}
int main() {
cin >> n >> m >> k;
for(int i = 1; i <= m; i++) {
int a, b, c;
cin >> a >> b >> c;
edges[i] = { a,b,c };
}
bellman_ford();
// 存在两个都不与起点联通，但彼此联通，在暴力遍历的途中更新了对方的距离，故应该用 > INF / 2来判断
if (dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
else cout << dist[n] << endl;
return 0;
}
模版
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
// st数组表示是否在队列中，队列表示正等待更新距离的点，只有这些点有权更新其他点的距离
bool st[N];
// 邻接表存图
void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void 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:false
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;
}
}
}
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
spfa();
if (dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << dist[n] << endl;
return 0;
}
spfa判断负环
模版(多源最短路)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 1e9;
int n, m, Q;
int dist[N][N];
void Floyd() {
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main() {
cin >> n >> m >> Q;
// 初始化距离，双层循环，同一个点距离为0，不同点之间距离为INF
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
dist[i][j] = (i == j ? 0 : INF);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
dist[a][b] = min(dist[a][b], c);
}
Floyd();
while (Q--) {
int a, b;
cin >> a >> b;
if (dist[a][b] > INF / 2) cout << "impossible" << endl;
else cout << dist[a][b] << endl;
}
return 0;
}
模板
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int dist[N], g[N][N];
bool st[N];
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;
}
}
// 若不是第一个点(第一个点没有已经确定的点，不谈论距离) 且距离为INF，则不联通
if (i && dist[t] == INF) return INF;
// 同理，从第二个点开始计算距离
if (i) res += dist[t];
st[t] = true;
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 u, v, w;
cin >> u >> v >> w;
g[u][v] = min(g[u][v], w);
}
int t = Prim();
if (t == INF) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
模版(稀疏图)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010, M = 200010, INF = 0x3f3f3f3f;
int n, m;
int p[N];
struct Edge
{
int a, b, w;
bool operator<(const Edge& other)const {
return w < other.w;
}
}edges[M];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int Kruskal() {
sort(edges, edges + m);
int res = 0, cnt = 0;
for (int i = 0; i < m; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) {
p[a] = b;
res += w;
cnt++;
}
}
// cnt < n - 1 说明没有将所有的点合并为同一个集合，则不联通
if (cnt < n - 1) return INF;
else return res;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
edges[i] = { a,b,w };
}
int t = Kruskal();
if (t == INF) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
模版
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int n, m;
int color[N];
int h[N], e[M], ne[M], idx;
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;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!color[j]) {
if (!dfs(j, 3 - c)) return false;
}
else if (color[j] == c) 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);
}
bool flag = true;
// 注意要对所有点都试一遍，只要有一个点冲突就不行
for (int i = 1; i <= n; i++) {
if (!color[i]) {
if (!dfs(i, 1)) {
flag = false;
break;
}
}
}
if (flag) cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 100010;
int n1, n2, k;
int e[N], ne[N], h[N], idx;
int match[N];
bool st[N];
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]) continue;
st[j] = true;
if (match[j] == 0 || find(match[j])) {
match[j] = x;
return true;
}
}
return false;
}
int main() {
cin >> n1 >> n2 >> k;
memset(h, -1, sizeof h);
while (k--) {
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
for (int i = 1; i <= n1; i++) {
memset(st, false, sizeof st);
if (find(i)) res++;
}
cout << res << endl;
return 0;
}