1熬北，DFS
深度優(yōu)先搜索疙描，代表題目有全排列、n皇后等讶隐。
DFS常見題目
2起胰，BFS
1）初始化隊(duì)列q
2）當(dāng)隊(duì)列不為空，取出隊(duì)頭元素巫延，擴(kuò)展隊(duì)頭
while (q不為空)
{
t = q.front();
q.pop();
擴(kuò)展t
}
3效五，樹與圖的存儲
樹是一種特殊的圖，與圖的存儲方式相同炉峰。
對于無向圖中的邊ab畏妖，存儲兩條有向邊a->b, b->a。
因此我們可以只考慮有向圖的存儲疼阔。
(1) 鄰接矩陣：g[a][b] 存儲邊a->b
(2) 鄰接表：
// 對于每個(gè)點(diǎn)k戒劫，開一個(gè)單鏈表，存儲k所有可以走到的點(diǎn)婆廊。h[k]存儲這個(gè)單鏈表的頭結(jié)點(diǎn)
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迅细，樹與圖的遍歷
時(shí)間復(fù)雜度 O(n+m)，n 表示點(diǎn)數(shù)淘邻，m 表示邊數(shù)
(1) 深度優(yōu)先遍歷
int dfs(int u)
{
st[u] = true; // st[u] 表示點(diǎn)u已經(jīng)被遍歷過
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
(2) 寬度優(yōu)先遍歷
queue<int> q;
st[1] = true; // 表示1號點(diǎn)已經(jīng)被遍歷過
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; // 表示點(diǎn)j已經(jīng)被遍歷過
q.push(j);
}
}
}
5茵典，拓?fù)渑判?/h3>
時(shí)間復(fù)雜度 O(n+m)，n 表示點(diǎn)數(shù)列荔，m 表示邊數(shù)
/*
有向無環(huán)圖一定是拓?fù)湫蛄?有向有環(huán)圖一定不是拓?fù)湫蛄? 1,一個(gè)有向圖敬尺，如果圖中有入度為 0 的點(diǎn)，就把這個(gè)點(diǎn)刪掉贴浙，同時(shí)也刪掉這個(gè)點(diǎn)所連的邊砂吞。
2,一直進(jìn)行上面出處理，如果所有點(diǎn)都能被刪掉崎溃，則這個(gè)圖可以進(jìn)行拓?fù)渑判颉?*/
#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創(chuàng)建鄰接表蜻直，d[i]表示下標(biāo)為i的點(diǎn)的入度（有多少條邊指向i）
int h[N], e[N], ne[N], idx, d[N];
int n, m;
//q是寬搜所用的隊(duì)列，res記錄符合入度為0的點(diǎn)
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的點(diǎn)入隊(duì)
for (int i = 1; i <= n; i++)
if (!d[i])
q.push(i);
while (q.size()) {
auto t = q.front();
q.pop();
//記錄隊(duì)里的元素
res.push_back(t);
//遍歷t的所有邊
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
//如果刪去t指向j的邊袁串，如果此時(shí)j的入度為0概而，就入隊(duì)
if (--d[j] == 0)
q.push(j);
}
}
//如果n個(gè)點(diǎn)都可以變?yōu)槿攵葹?，說明是拓?fù)鋱D
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算法
時(shí)間復(fù)雜是 O(n2+m)赎瑰，n 表示點(diǎn)數(shù)，m 表示邊數(shù)
/*
樸素dijkstra：
1破镰，初始化距離數(shù)組dist[1] = 0, dist[i] = 0x3f;
st：當(dāng)前已經(jīng)確定最短距離的點(diǎn)
2餐曼，迭代n次
1) 找到當(dāng)前未在st中標(biāo)記過且離起點(diǎn)最近的點(diǎn)t
2) 將該點(diǎn)t進(jìn)行標(biāo)記
3) 用t更新其他點(diǎn)的距離
*/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510;
//g[i][j]鄰接矩陣压储，因?yàn)槭浅砻軋D，所以需要用鄰接矩陣存儲源譬，表示從i到j(luò)的權(quán)值
//dist[i]表示下標(biāo)為i的點(diǎn)到第一個(gè)點(diǎn)的距離
int g[N][N], dist[N];
//st[i]表示下標(biāo)為i的點(diǎn)的距離是否確定
bool st[N];
int n, m;
int dijsktra() {
//初始化距離為正無窮
memset(dist, 0x3f, sizeof dist);
//第一個(gè)點(diǎn)到本身的距離為0
dist[1] = 0;
//迭代n次
for (int i = 0; i < n; i++) {
//
int t = -1;
//遍歷dist數(shù)組集惋，找到?jīng)]有確定最短路徑的節(jié)點(diǎn)中距離起點(diǎn)最近的點(diǎn)t
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
//確定t后更新狀態(tài)
st[t] = true;
//用最小的點(diǎn)t去更新其他的點(diǎn)到起點(diǎn)的距離
for (int j = 1; j <= n; j++) {
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
//如果起點(diǎn)到達(dá)不了n號節(jié)點(diǎ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;
//如果發(fā)生重邊就只需要保留最短的一條邊
g[a][b] = min(g[a][b], c);
}
cout << dijsktra() << endl;
return 0;
}
6.2踩娘，堆優(yōu)化版dijkstra
時(shí)間復(fù)雜度 O(mlogn)刮刑，n 表示點(diǎn)數(shù)，m 表示邊數(shù)
#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;
//將下標(biāo)為1的點(diǎn)插入小根堆养渴，first表示距離雷绢，second表示下標(biāo)
heap.push({0, 1});
while (heap.size()) {
//取不在集合st中距離最短的點(diǎn)，因?yàn)樾「岩呀?jīng)排序厚脉，所以只需要取堆頂元素
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(luò)的距離，就更新值的大猩倒ぁ；
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
//更新距離之后將該點(diǎn)的距離加入到堆中
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算法
時(shí)間復(fù)雜度 O(nm)中捆，n 表示點(diǎn)數(shù)，m 表示邊數(shù)
/*
bellman_ford算法：
1坊饶，循環(huán)k次
2泄伪，遍歷所有的邊
3，更新距離數(shù)組
*/
#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++) {
//這里需要備份匿级，防止影響到下一個(gè)點(diǎn)
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是因?yàn)?x3f3f3f3f是一個(gè)確定的值蟋滴，會受到其他數(shù)值影響，
只要判斷和0x3f3f3f3f一個(gè)量級即可痘绎。
返回0x3f3f3f3f是因?yàn)槿绻祷?1津函，可能導(dǎo)致與正確答案沖突
*/
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 算法（隊(duì)列優(yōu)化的Bellman-Ford算法）
時(shí)間復(fù)雜度 平均情況下 O(m)孤页，最壞情況下 O(nm)尔苦，n 表示點(diǎn)數(shù)，m 表示邊數(shù)
/*
spfa算法：
1行施，建立一個(gè)隊(duì)列允坚，初始時(shí)隊(duì)列里只有起始點(diǎn)
2，再建立一個(gè)數(shù)組記錄起始點(diǎn)到所有點(diǎn)的最短路徑（該表格的初始值要賦為極大值蛾号，該點(diǎn)到他本身的路徑賦為0）
3稠项，再建立一個(gè)數(shù)組，標(biāo)記點(diǎn)是否在隊(duì)列中
4鲜结，隊(duì)頭不斷出隊(duì)展运，計(jì)算始點(diǎn)起點(diǎn)經(jīng)過隊(duì)頭到其他點(diǎn)的距離是否變短活逆，如果變短且被點(diǎn)不在隊(duì)列中，則把該點(diǎn)加入到隊(duì)尾
5乐疆，重復(fù)執(zhí)行直到隊(duì)列為空
6划乖，在保存最短路徑的數(shù)組中，就得到了最短路徑
*/
#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);
//標(biāo)記點(diǎn)已經(jīng)在隊(duì)列中
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];
//如果始點(diǎn)起點(diǎn)經(jīng)過隊(duì)頭到其他點(diǎn)的距離變短
if (dist[j] > dist[t] + w[i]) {
//更新距離
dist[j] = dist[t] + w[i];
//如果該點(diǎn)不在隊(duì)列挤土，加入隊(duì)列
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算法
時(shí)間復(fù)雜度是 O(n3)，n 表示點(diǎn)數(shù)
#include <bits/stdc++.h>
using namespace std;
const int N = 210;
//鄰接矩陣仰美，d[i][j]表示i到j(luò)的最短距離
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]);
}
/*動(dòng)態(tài)規(guī)劃的思想*/
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算法
時(shí)間復(fù)雜度是 O(n2+m)咖杂，n 表示點(diǎn)數(shù)庆寺，m 表示邊數(shù)
#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;
//循環(huán)n次
for (int i = 0; i < n; i++) {
int t = -1;
//找到?jīng)]有在生成樹中并且離生成樹距離最短的點(diǎn)
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
}
//如果這個(gè)點(diǎn)是孤立點(diǎn)，返回INF
if (i && dist[t] == INF) return INF;
//否則加入答案
if (i) res += dist[t];
//標(biāo)記已經(jīng)加到生成樹
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的祖先節(jié)點(diǎn)
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int Kruskal() {
//根據(jù)權(quán)值對邊進(jìn)行從小到大排序
sort(e, e + m);
//初始化并查集
for (int i = 1; i <= n; i++) p[i] = i;
//res記錄最小生成樹權(quán)重之和懦尝，cnt記錄生成樹的邊數(shù)量
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不在一個(gè)集合壤圃，就加入到集合中陵霉，res增加ab邊的權(quán)值，cnt增加一條邊
if (a != b) {
res += w;
cnt++;
p[a] = b;
}
}
//n個(gè)節(jié)點(diǎ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，染色法判別二分圖
時(shí)間復(fù)雜度是 O(n+m)冲杀，n 表示點(diǎn)數(shù)效床，m 表示邊數(shù)
#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++;
}
//把節(jié)點(diǎn)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];
//如果這個(gè)點(diǎn)沒有染色
if (!color[j]) {
//進(jìn)行染色，如果染色不成功权谁，不是二分圖
if (!dfs(j, 3 - v)) return false;
}
//如果這個(gè)點(diǎn)已經(jīng)染色剩檀，但是顏色不是相反的顏色，沖突
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);
}
//遍歷每一個(gè)點(diǎn)
for (int i = 1; i <= n; i++) {
//如果這個(gè)點(diǎn)沒有染色
if (!color[i]) {
//進(jìn)行染色闯传，如果染色不成功谨朝，不是二分圖
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已經(jīng)有男生在追了
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的男朋友找到另一個(gè)女生
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++) {
//因?yàn)槊恳惠喣猩婚_始都沒有追女生字币，所以每次st都為false
memset(st, false, sizeof st);
//如果找到了，res++
if (find(i)) res++;
}
cout << res << endl;
return 0;
}
