DFS简单例题
#include <bits/stdc++.h>
using namespace std;
int n;
int path[10];
bool vis[10];
void dfs(int x)
{
if(x == n)
{
for(int i = 1; i <= n; i ++ )
{
cout << path[i] << ' ';
}
cout << endl;
return ;
}
for(int i = 1; i <= n; i ++ )
{
if(!vis[i])
{
vis[i] = 1;
path[x + 1] = i;
dfs(x + 1);
path[x + 1] = 0;
vis[i] = 0;
}
}
return ;
}
int main()
{
cin >> n;
dfs(0);
return 0;
}
n-皇后
一行行的枚举
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n;
char g[N][N];
int col[N], dj[N], udj[N];
void dfs(int h)
{
if(h == n + 1)
{
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ ) cout << g[i][j];
cout << endl;
}
cout << endl;
return ;
}
for(int i = 1; i <= n; i ++ )
{
if(!col[i] && !udj[h - i + n] && !dj[h + i])
{
g[h][i] = 'Q';
col[i] = udj[h - i + n] = dj[h + i] = 1;
dfs(h + 1);
col[i] = udj[h - i + n] = dj[h + i] = 0;
g[h][i] = '.';
}
}
return ;
}
int main()
{
cin >> n;
// 一定先要初始化 不然能拿的就只有串的头 后面相当于没有定义 不存在
// 想要参悟dfs的过程 可以g[i][j] = '#'
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ ) g[i][j] = '.';
}
dfs(1);
return 0;
}
一个个格子的枚举
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int n;
char g[N][N];
int row[N], col[N], dj[N], udj[N];
void dfs(int x, int y, int s)
{
if(y > n) x ++ , y %= n;
if(x == n + 1)
{
if(s == n)
{
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ ) cout << g[i][j];
cout << endl;
}
cout << endl;
}
return ;
}
// 这个格子不放皇后
dfs(x, y + 1, s);
// 想放 看能不能放
if(!row[x] && !col[y] && !dj[y + x] && !udj[y - x + n])
{
g[x][y] = 'Q';
row[x] = col[y] = dj[y + x] = udj[y - x + n] = 1;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dj[y + x] = udj[y - x + n] = 0;
g[x][y] = '.';
}
return ;
}
int main()
{
cin >> n;
// 一定先要初始化 不然能拿的就只有串的头 后面相当于没有定义 不存在
// 想要参悟dfs的过程 可以g[i][j] = '#'
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ ) g[i][j] = '.';
}
dfs(1, 1, 0);
return 0;
}
走迷宫-简单的BFS
八数码-把状态转移为点-然后BFS
#include <bits/stdc++.h>
using namespace std;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int bfs(string x)
{
queue<string> q;
// 普通map会T
unordered_map<string, int> d;
q.push(x); d[x] = 0;
while(q.size())
{
auto t = q.front(); q.pop();
if(t == "12345678x") return d[t];
int dis = d[t];
int po = t.find('x');
int px = po / 3;
int py = po % 3;
for(int i = 0; i <= 3; i ++ )
{
int xx = px + dx[i];
int yy = py + dy[i];
if(xx >= 0 && xx < 3 && yy >= 0 && yy < 3)
{
int npo = xx * 3 + yy;
swap(t[po], t[npo]);
if(!d.count(t))
{
q.push(t);
d[t] = dis + 1;
}
swap(t[po], t[npo]);
}
}
}
return -1;
}
int main()
{
string x, y;
for(int i = 1; i <= 9; i ++ )
{
cin >> y;
x += y;
}
cout << bfs(x) << endl;
return 0;
}
树的重心-图的深度优先遍历
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
bool st[N];
int ans = 0x3f3f3f3f;
vector< vector<int> > g(N);
int dfs(int x)
{
int cnt = 0;
int sum = 1;
for(int i = 0; i < g[x].size(); i ++ )
{
if(!st[g[x][i]])
{
st[g[x][i]] = 1;
int xx = dfs(g[x][i]);
sum += xx;
cnt = max(cnt, xx);
st[g[x][i]] = 0;
}
}
cnt = max(cnt, n - sum);
ans = min(ans, cnt);
return sum;
}
int main()
{
cin >> n;
for(int i = 1; i <= n - 1; i ++ )
{
int x, y; cin >> x >> y;
g[x].emplace_back(y);
g[y].emplace_back(x);
}
st[1] = 1; dfs(1);
cout << ans << endl;
return 0;
}
图中点的层次-图的广度优先遍历
拓扑排序-广搜应用
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int main()
{
int n, m; cin >> n >> m;
vector<int> id(n + 10, 0);
vector< vector<int> > g(n + 10);
for(int i = 1; i <= m; i ++ )
{
int x, y; cin >> x >> y;
g[x].emplace_back(y);
id[y] ++ ;
}
queue<int> q, qq;
for(int i = 1; i <= n; i ++ )
{
if(!id[i]) q.push(i);
// cout << id[i] << ' ';
}
while(q.size())
{
auto t = q.front(); q.pop();
qq.push(t);
for(int i = 0; i < g[t].size(); i ++ )
{
id[g[t][i]] -- ;
if(!id[g[t][i]]) q.push(g[t][i]);
}
}
if(qq.size() < n) cout << -1 << endl;
else
{
while(qq.size())
{
cout << qq.front() << ' ';
qq.pop();
}
}
return 0;
}
最短路算法总结
——单源最短路
————边权皆正
——————朴素Dijkstra O(n^2)
——————堆优化Dijkstra O(mlogn)
————有负权边
——————Bellman-Ford O(nm)
——————SPFA 一般O(m),最坏O(nm) // 最常用 Dijkstra能写的大部分题SPFA都能写 卡了再说
——多源最短路 Floyd O(n^3)
朴素dijkstra
#include <string.h>
#include <iostream>
#include <math.h>
using namespace std;
const int N = 505;
int g[N][N] = {0};
int dist[N] = {0};
bool st[N] = {0};
int n, m;
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 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;
}
}
st[t] = true;
for(int j = 1; j <= n; j++)
{
dist[j] = min(dist[j], dist[t] + g[t][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, c; cin>>a>>b>>c;
g[a][b] = min(g[a][b], c);
}
int t = dijkstra();
cout<<t<<'\n';
return 0;
}
堆优化Dijkstra
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
const int N = 150000 + 10;
int n, m;
bool st[N];
int dist[N];
vector<PII> g[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
priority_queue< PII, vector<PII>, greater<PII> > q;
dist[1] = 0;
q.push({0, 1});
while(q.size())
{
auto t = q.top(); q.pop();
int dis = t.first;
int id = t.second;
if(st[id]) continue;
st[id] = 1;
for(int i = 0; i < g[id].size(); i ++ )
{
dist[g[id][i].first] = min(dist[g[id][i].first], dis + g[id][i].second);
q.push({dist[g[id][i].first], g[id][i].first });
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i ++ )
{
int x, y, c; cin >> x >> y >> c;
g[x].emplace_back(y, c);
}
int t = dijkstra();
cout << t << endl;
return 0;
}
除了这题一般用不上的Bellman-Ford
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 10;
const int M = 1e4 + 10;
int n, m, k;
int dist[N], last[N];
struct Edge
{
int x, y, w;
};
Edge a[M];
void flod()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 1; i <= k; i ++ )
{
memcpy(last, dist, sizeof last);
for(int j = 1; j <= m; j ++ )
{
auto t = a[j];
dist[t.y] = min(dist[t.y], last[t.x] + t.w);
}
}
if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
else cout << dist[n] << endl;
}
int main()
{
cin >> n >> m >> k;
for(int i = 1; i <= m; i ++ )
{
int x, y, w; cin >> x >> y >> w;
a[i].x = x; a[i].y = y; a[i].w = w;
}
flod();
return 0;
}
SPFA既能求最短路
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
const int N = 1e5 + 10;
int n, m, st[N], dist[N];
vector<PII> g[N];
void spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1); st[1] = 1;
while(q.size())
{
int t = q.front(); q.pop(); st[t] = 0;
for(int i = 0; i < g[t].size(); i ++ )
{
int y = g[t][i].first;
int w = g[t][i].second;
if(dist[y] > dist[t] + w)
{
dist[y] = dist[t] + w;
if(!st[y])
{
st[y] = 1; q.push(y);
}
}
}
}
if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible" << endl;
else cout << dist[n] << endl;
return ;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i ++ )
{
int x, y, w; cin >> x >> y >> w;
g[x].emplace_back(y, w);
}
spfa();
}
SPFA还能判负环
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
const int N = 1e5 + 10;
int n, m, st[N], cnt[N], dist[N];
vector<PII> g[N];
bool spfa()
{
queue<int> q;
for(int i = 1; i <= n; i ++ )
{
q.push(i); st[i] = 1;
}
while(q.size())
{
int t = q.front(); q.pop(); st[t] = 0;
for(int i = 0; i < g[t].size(); i ++ )
{
int y = g[t][i].first;
int w = g[t][i].second;
if(dist[y] > dist[t] + w)
{
dist[y] = dist[t] + w;
cnt[y] = cnt[t] + 1;
if(cnt[y] >= n) return 1;
if(!st[y])
{
st[y] = 1; q.push(y);
}
}
}
}
return 0;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= m; i ++ )
{
int x, y, w; cin >> x >> y >> w;
g[x].emplace_back(y, w);
}
if( spfa() ) cout << "Yes" << endl ;
else cout << "No" << endl;
return 0;
}
Floyd求最短路
#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 10;
const int M = 20000 + 10;
const int INF = 0x3f3f3f3f;
int n, m, Q;
int g[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 ++ )
{
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
return ;
}
int main()
{
cin >> n >> m >> Q;
for(int i = 1; i <= n; i ++ )
{
for(int j = 1; j <= n; j ++ )
{
if(i == j) g[i][j] = 0;
else g[i][j] = INF;
}
}
for(int i = 1; i <= m; i ++ )
{
int x, y, w; cin >> x >> y >> w;
g[x][y] = min(g[x][y], w);
}
floyd();
for(int i = 1; i <= Q; i ++ )
{
int x, y; cin >> x >> y;
if(g[x][y] > INF / 2) cout << "impossible" << endl;
else cout << g[x][y] << endl;
}
return 0;
}
最小生成树算法
——Prim
————朴素版 O(n^2)
————堆优化版 O(mlogn)
——Kruskal O(mlogm)
Prim朴素版
#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 10;
bool st[N];
int n, m, g[N][N], dist[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
int ans = 0;
for(int i = 0; i < n; i ++ )
{
int t = -1;
for(int j = 1; j <= n; j ++ )
{
if( (!st[j]) && (t == -1 || dist[j] < dist[t]) ) t = j;
}
st[t] = 1;
if(i && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
if(i)
{
ans += dist[t];
}
for(int j = 1; j <= n; j ++ )
{
dist[j] = min(dist[j], g[t][j]);
}
}
return ans;
}
int main()
{
memset(g, 0x3f, sizeof g);
cin >> n >> m;
for(int i = 1; i <= m; i ++ )
{
int x, y, w; cin >> x >> y >> w;
g[x][y] = g[y][x] = min(g[x][y], w);
}
int t = prim();
if(t == 0x3f3f3f3f) cout << "impossible" << endl;
else cout << t << endl;
return 0;
}
Kruskal