目录
DFS
用dfs(递归)搜索每一种情况
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N];
bool st[N];
void dfs(int u)
{
cout<<u<<endl;
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); // 递归的过程就是dfs的过程
cout<<u<<" "<<i<<" "<<endl;
st[i] = false; // 回溯, 将路径清空
}
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
}#include <iostream>
using namespace std;
const int N = 11;
int n;
char g[N][N];
bool row[N],col[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++) puts(g[i]);
puts("");
}
return;
}
// 不放皇后
dfs(x, y+1, s);
// 放皇后
if(!row[x] && !col[y] && !dg[x+y] && !udg[n-y+x])
{
g[x][y] = 'Q';
row[x] = col[y] = dg[x+y] = udg[n-y+x] = true;
dfs(x, y+1, s+1);
row[x] = col[y] = dg[x+y] = udg[n-y+x] = false;
g[x][y] = '.';
}
}
int main()
{
cin>>n;
for(int i = 0; i<n; i++){
for(int j = 0; j<n; j++) g[i][j] = '.';
}
dfs(0,0,0);
return 0;
}
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5+10, M = 2*N;
int e[M],ne[M],h[N],idx;
int n,m,ans = N;
bool st[N];
void add(int a,int b) // 插入一条边
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++; // 头插法
}
// dfs 框架
/*
void dfs(int u){
st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]) {
dfs(j);
}
}
}
*/
int dfs(int u)
{
st[u] = true; // 用st来表示节点状态, 是否被访问过
int sum = 1, res = 0; // sum表示以u为根 子节点的数量, res表示 删除某个点后, 最大的联通点的数量
for(int i = h[u]; i != -1; i = ne[i]) // 遍历树
{
int j = e[i]; // 用j来记录该节点的编号
if(!st[j]) // 如果该节点没有被搜过
{
int s = dfs(j); // 则搜索该节点
res = max(res, s); // res记录最大的联通点数量
sum += s; // 记录以u为根的子节点数
}
}
res = max(res, n - sum); // res记录最大的联通点数量
ans = min(res, ans); // 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;
}BFS
利用队列来实现bfs
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n,m;
int g[N][N], d[N][N];
queue<PII> q; // 利用队列来实现bfs
int bfs()
{
memset(d, -1, sizeof d); // 距离全存为-1 来证明没有被走过
q.push({0,0}); // 将开始的点放入队列
d[0][0] = 0; // 开始的点距离为0
int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0}; // 用向量来表示四个方向(也可以写四个if else)
while(q.size())
{
auto t = q.front(); // 取队头元素为要走的点
q.pop(); // 取完后弹出
for(int i = 0; i<4; i++) // 枚举四个方向
{
int x = t.first + dx[i], y = t.second + dy[i];
if(x>=0 && x<n && y>=0 && y<m && g[x][y] == 0 && d[x][y] == -1) // 方向上的点合理存在且没有被走过
{
d[x][y] = d[t.first][t.second] + 1;
q.push({x,y});
}
}
}
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 <unordered_map>
#include <queue>
using namespace std;
int bfs(string start)
{
// 定义最终状态
string end = "12345678x";
// 利用队列实现bfs
queue<string> q;
// 哈希表查找每个状态的对应步数
unordered_map<string, int> d;
// 初始化
q.push(start);
d[start] = 0;
// 四个向量代表四个方向
int dx[4] = {0,-1,0,1}, dy[4] = {-1,0,1,0};
while(q.size())
{
auto t = q.front();
q.pop();
if(t == end) return d[t];
int dist = d[t];
// 将一维坐标转化为二维坐标
int k = t.find('x');
int x = k / 3, y = k % 3;
for(int i = 0; i<4; i++)
{
int a = x + dx[i], b = y + dy[i];
if(a >= 0 && a < 3 && b >= 0 && b < 3)
{
// 二维转一维, 并交换
swap(t[k], t[a*3 + b]);
// 如果t没有被搜过
if(!d.count(t))
{
d[t] = dist + 1;
q.push(t);
}
swap(t[k], t[a*3 + b]);
}
}
}
return -1;
}
int main()
{
string start;
// 读入9个字符, 过滤空格
for (int i = 0; i < 9; i ++ )
{
char s;
cin >> s;
start += s;
}
// bfs搜索最短路
cout<<bfs(start)<<endl;
return 0;
}#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int n,m;
int h[N],e[2*N],ne[2*N],idx;
int d[N],q[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs()
{
int tt = 0, hh = 0;
q[0] = 1; // 初始点1入队
d[1] = 0; // 初始距离为0
while(hh <= tt) // bfs模板 while(队列不空){点入队; 拓展}
{
int t = q[hh++];
for(int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if(d[j] == -1)
{
d[j] = d[t] + 1;
q[++tt] = j;
}
}
}
return d[n];
}
int main()
{
cin>>n>>m;
memset(h, -1, sizeof h); // 初始化 -1表示没有这个点
memset(d, -1, sizeof d); // 初始化 -1表示没有被搜过
for(int i = 0; i<m; i++)
{
int a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs()<<endl;
}拓扑排序
// 一个有向无环图(拓补图) 一定存在一个入度为0的点
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5+10;
int n,m;
int h[N],e[2*N],ne[2*N],idx;
int d[N],q[N];
void add(int a,int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int topsort()
{
int hh = 0, tt = -1;
for(int i = 1; i<=n; i++)
{
if(!d[i]) q[++tt] = i; // 将入度为0的点直接入队做队头
}
while(hh<=tt) // 若是有环图, while循环将会提前结束, 使得tt<n-1
{
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; // 判断是否所有的点都入队, 即所有点都能被入度-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] ++; // a-->b, b的入度++
}
if(topsort())
{
for(int i = 0; i<n; i++) cout<<q[i]<<" "; // 入队的顺序就是拓补序
}
else puts("-1");
return 0;
}
最短路
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 550;
int n,m;
int g[N][N]; // 用邻接矩阵存稠密图 , g[a][b] = c 表示a到b的距离是c
int dist[N]; // 存每个点到原点的最短距离
bool st[N]; // 点的状态
int dijkstra()
{
// 初始化距离为最大
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 初始化起点为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++)
{
// 一开始 t = 1, 即每个点都是直接到源点;
// 后更新 t, 再用t更新其它的点
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin>>n>>m;
// 初始化最大值, 表示到不了源点, 在用dijkstra迭代更新
memset(g, 0x3f, sizeof g);
// 用邻接矩阵存稠密图 , g[a][b] = c 表示a到b的距离是c
for(int i = 0; i<m; i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = min(g[a][b], c);
}
int t = dijkstra();
printf("%d", t);
return 0;
}#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6+10;
int n,m;
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 dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0,1});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int d = t.first, ver = t.second;
if(st[ver]) continue; // 如果这个点找过了, 就跳过
st[ver] = true; // 更新点的状态
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()
{
cin>>n>>m;
// 初始化点为不存在
memset(h, -1, sizeof h);
while(m -- )
{
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
int t = dijkstra();
printf("%d", t);
return 0;
}#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 1e4+10;
struct Edge
{
int a,b,w;
}edges[M];
int n,k,m;
// 每次迭代是迭代边数, 从一条边迭代, 两条边迭代, 避免出现在一条边迭代时, 实现了两条边的过程(串联)
// 要用backup来备份迭代前的结果
int dist[N],backup[N];
void bellman_ford()
{
memset(dist, 0x3f, sizeof dist); // 初始化距离为无穷大(0x3f3f3f3f)
dist[1] = 0; // 源点距离0
for(int i = 0; i<k; i++) // 有负权边, 最多更新k条边
{
memcpy(backup, dist, sizeof dist); // 初始化备份
for(int j = 0; j<m; j++)
{
auto e = edges[j];
dist[e.b] = min(dist[e.b], backup[e.a] + e.w);
}
}
if(dist[n] > 0x3f3f3f3f / 2) cout<<"impossible";
else cout<<dist[n]<<endl;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 0; i<m; i++)
{
int a,b,w;
scanf("%d%d%d",&a, &b, &w);
edges[i] = {a, b, w};
}
bellman_ford();
return 0;
}spfa算法
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+10;
int n,m;
int h[N],w[N],e[N],ne[N],idx; // 邻接表存图
int dist[N];
bool st[N];
void insert(int a,int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void spfa()
{
memset(dist, 0x3f, sizeof dist);
queue<int> q;
dist[1] = 0;
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;
}
}
}
}
if(dist[n] == 0x3f3f3f3f) puts("impossible");
else printf("%d\n", dist[n]);
}
int main()
{
scanf("%d%d",&n,&m);
memset(h, -1, sizeof h);
while(m --)
{
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
insert(a, b, c);
}
spfa();
return 0;
}#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1e5+10;
int n,m;
int h[N],w[N],e[N],ne[N],idx; // 邻接表存图
int dist[N], cnt[N]; // cnt存边数
bool st[N];
void insert(int a,int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
bool spfa()
{
queue<int> q;
// 并不是求最短路, 不需要初始化
// 负环可能从1点到不了, 就把所有点放入队列
for(int i = 1; i<=n; i++)
{
q.push(i);
st[i] = 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];
cnt[j] = cnt[t] + 1; // 每次更新加一条边
// 若更新后的边大于n, 则有n+1的点, 又只有n个点, 则存在负环
if(cnt[j] >= n) return true;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h, -1, sizeof h);
while(m --)
{
int a,b,c;
scanf("%d%d%d", &a, &b, &c);
insert(a, b, c);
}
if(spfa()) puts("Yes");
else puts("No");
return 0;
}#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 210, INF = 1e9;
int n,m,Q;
int d[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++)
{
d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // 动态规划思想
}
}
}
}
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;
scanf("%d%d%d", &a, &b, &c);
d[a][b] = min(d[a][b], c);
}
floyd();
while(Q -- )
{
int a,b;
scanf("%d%d", &a, &b);
int t = d[a][b];
if(t > INF / 2) puts("impossible");
else cout<<t<<endl;
}
return 0;
}最小生成树和二分图
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N]; // 存的是点到集合的距离 (dijkstra存的是点之间的距离)
bool st[N]; // 已找好的点放入st中
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;
// 先更新 res , 若存在自环, 下面的循环会把dist[t]更新了
if(i) res += dist[t];
for(int j = 1; j<=n; j++) dist[j] = min(dist[j], g[t][j]);
// 更新完将t 存入st[]
st[t] = true;
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
memset(g, 0x3f, sizeof g);
while(m -- )
{
int a,b,c;
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);
return 0;
}#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+10;
int n,m;
// 用并查集来连通点, p[N]为并查集中的祖宗节点
int p[N];
struct Edge{
int a,b,w;
bool operator< (const Edge &W)const
{
return w<W.w;
}
}edges[N];
int find(int x)
{
// 并查集模板
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
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};
}
sort(edges, edges + m);
for(int i = 0; i<n; i++) p[i] = i;
// res 存的最小生成树的边权和, cnt存的是有多少边
int res = 0, cnt = 0;
for(int i = 0; i<m; i++)
{
auto e = edges[i];
int a = e.a, b = e.b, w = e.w;
a = find(a), b = find(b);
if(a != b)
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if(cnt < n-1) puts("impossible");
else printf("%d\n", res);
return 0;
}#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+10, M = 2*N;
int n,m;
int h[N],e[M],ne[M],idx;
int color[N];
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])
{
// 染相反的色
// 失败返回false
if(!dfs(j, 3 - c)) return false;
}
// 若颜色相同返回false
else if(color[j] == c) return false;
}
return true;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while(m -- )
{
int a,b;
scanf("%d%d", &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) puts("Yes");
else puts("No");
return 0;
}#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 1e5+10;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];
int n1,n2,m;
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 --)
{
int a,b;
cin>>a>>b;
add(a, b);
}
int res = 0;
// 对于每一个男生(n1节点) 去匹配一个女生(n2节点)
for(int i = 1; i<=n1; i++)
{
memset(st, false, sizeof st);
if(find(i)) res ++;
}
cout<<res<<endl;
return 0;
}