一.DFS
1.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++)
cout << path[i] <<" ";
cout << endl;
return ;
}
for(int i = 1;i <= n;i++){
if(!st[i]){
st[i] = true;
path[u] = i;
dfs(u + 1);
st[i] = false;
}
}
}
int main(){
cin >> n;
dfs(0);
}
1.2 n皇后问题
#include <iostream>
using namespace std;
int n;
const int N = 10;
char g[N][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]);
cout << endl;
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(){
cin >> n;
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
g[i][j] = '.';
dfs(0);
return 0;
}
二.BFS
2.1 走迷宫
using PII = pair<int,int>;
const int N = 110;
int n,m;
int g[N][N];
int d[N][N];
queue<PII> q;
int bfs(){
q.push({0,0});
memset(d,-1,sizeof d);
d[0][0] = 1;
int next[4][2] = {
{1,0},
{-1,0},
{0,1},
{0,-1}
};
while(!q.empty()){
auto t = q.front();
q.pop();
for(int i = 0;i < 4;i++){
int tx = t.first + next[i][0];
int ty = t.second + next[i][1];
if(tx >= 0 && tx< n && ty >= 0 && ty< m&& g[tx][ty] == 0 && d[tx][ty] == -1){
d[tx][ty] = d[t.first][t.second] + 1;
q.push({tx,ty});
}
}
}
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;
}
2.2 八数码
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int direction[4][2] = {
{0,1},
{0,-1},
{1,0},
{-1,0}
};
int bfs(string start){
queue<string> q;
unordered_map<string,int> d;
q.push(start);
d[start] = 0;
while(!q.empty()){
auto t = q.front();
q.pop();
int distance = d[t];
if(t == "12345678x") return distance;
int k = t.find('x');
int x = k / 3,y = k % 3;
for(int i = 0;i < 4;i++){
int a = x + direction[i][0];
int b = y + direction[i][1];
if(a >= 0 && a < 3 && b>= 0 && b < 3){
swap(t[k],t[a *3 + b]);
if(!d.count(t)){
d[t] = distance + 1;
q.push(t);
}
swap(t[k],t[a *3 + b]);
}
}
}
return -1;
}
int main(){
string start;
for(int i = 0;i < 3;i++)
for(int j = 0;j < 3;j++)
{
char c;
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}
三、树与图的遍历
3.1 树与图的深度优先遍历之树的重心
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010,M = N * 2;
int h[N];
int e[M];
int ne[M];
int idx;
bool st[N];
int ans = N;
int 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 sum = 1,res = 0;
for(int i = h[u];i != -1;i = ne[i]){
int j = e[i];
if(!st[j]){ //均为平级,所以需要循环遍历所有的平级子树 然后找到res最大值
int s = dfs(j);
res = max(res,s);
sum += s;
}
}
res = max(res , n - sum);
ans = min(ans,res); //每一层递归保证ans取得最小值
return sum;
}
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;
}
3.2 图的广度优先遍历之图中节点的层次
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
#include <unordered_map>
#include <iso646.h>
#include <queue>
using namespace std;
const int N = 1e5 + 10,M = N* 2;
int n,m;
int h[N],ne[M],e[M],idx;
queue<int> q;
int d[N];
void add(int a,int b){
e[idx] = b;ne[idx] = h[a],h[a] = idx++;
}
int bfs(){
q.push(1);
d[1] = 0;
while(!q.empty()){
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(d,-1,sizeof d);
memset(h,-1,sizeof h);
for(int i = 0;i < m;i++){
int a,b;
cin >> a >> b;
add(a,b);
}
cout << bfs() ;
return 0;
}
四、拓扑排序
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1E5 + 10,M = N* 2;
int n,m;
int h[N],ne[M],e[M],idx;
int q[N];
int d[N];
void add(int a,int b){
e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
bool topsport(){
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];
d[j]--;
if(d[j] == 0) q[++tt] = j;
}
}
return tt == n - 1;
}
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(topsport()){
for(int i = 0;i < n;i++) cout << q[i] <<" ";
}else{
cout << "-1";
}
return 0;
}
五、dijkstra算法
5.1朴素版dijkstra算法
#include<bits/stdc++.h>
using namespace std;
const int N = 510;
const int inf = 0x3f3f3f3f;
int mp[N][N], dis[100010];
int n,m;
bool st[N];
int dijkstra(){
memset(dis, 0x3f, sizeof dis);
dis[1] = 0;
for(int i = 1; i <= n - 1; ++i){
int t = -1;
for(int j = 1; j <= n; ++j){
if(!st[j] && (t == -1 || dis[t] > dis[j]))
t = j;
}
st[t] = true;
for(int j = 1; j <= n; ++j){
if(dis[j] > dis[t] + mp[t][j])
dis[j] = dis[t] + mp[t][j];
}
}
return dis[n] == inf ? -1 : dis[n];
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
mp[i][j] = (i == j ? 0 : inf);
int a,b,v;
for(int i = 1; i <= m; ++i){
scanf("%d%d%d",&a,&b,&v);
mp[a][b] = min(mp[a][b], v);
}
printf("%d\n", dijkstra());
return 0;
}
5.2堆优化版Dijkstra
#include<bits/stdc++.h>
using namespace std;
using PII = pair<int,int>;
const int N = 150010;
const int inf = 0x3f3f3f3f;
int dist[N], h[N], e[N], w[N], ne[N], idx;
int n,m;
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;
heap.push({0,1});
while(!heap.empty()){
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});
}
}
}
return dist[n] == inf ? -1: dist[n];
}
int main(){
memset(h, -1, sizeof h);
cin >> n >> m;
int a,b,v;
for(int i = 1; i <= m; ++i){
scanf("%d%d%d",&a,&b,&v);
add(a,b,v);
}
printf("%d\n", dijkstra());
return 0;
}
六、Bellman-ford算法
#include<iostream>
#include <cstring>
using namespace std;
const int N = 510,M = 10010;
int n,m,k;
int dist[N],backup[N];
struct Edge{
int a,b,w;
}edges[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 = edges[j].a,b = edges[j].b,w = edges[j].w;
dist[b] = min(dist[b],backup[a] + w);
}
}
if(dist[n] > 0x3f3f3f3f /2 ) return -1; //因为存在负的边权,但是不会减太多,所以是0x3f3f3f3f/2
return dist[n];
}
int main(){
cin >> n >> m >> k;
for(int i = 0;i < m;i++){
int a,b,w;
cin >> a >> b >> w;
edges[i] = {a,b,w};
}
int t = bellman_ford();
if(t == -1) puts("impossible");
else cout << t;
}
版权属于:superzhaoyang
本文链接:https://www.superzhaoyang.top/archives/39/
转载时须注明出处及本声明