week3 搜索与图论
DFS(深度优先搜索)
算法思想
一直走到底，十分执着
要结合回溯和剪枝
代码模板
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
例子
example 1 : 排列数字
给定一个整数
n
n
n
，将数字
1
∼
n
1∼n
1
∼
n
排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
#include<iostream>
using namespace std;
const int N=100;
int n;
bool flag[100];
int path[N];
void dfs(int a)
{
if(a == n)
{
for(int i=0;i<n;i++)
{
cout<<path[i]<<" ";
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++)
{
if(flag[i]==false)
{
flag[i]=true;
path[a]=i;
dfs(a+1);//注意是a+1而不是i+1
flag[i]=false;
}
}
}
int main()
{
cin>>n;
dfs(0);
return 0;
}
example 2 : n-皇后问题
n
−
n−
n
−
皇后问题是指将
n
n
n
个皇后放在
n
×
n
n×n
n
×
n
的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一3行、同一列或同一斜线上。
现在给定整数
n
n
n
，请你输出所有的满足条件的棋子摆法。
1、搜索方法一
#include<iostream>
using namespace std;
const int N=20;
int n;
char g[N][N];
int col[N],dj[N],udj[N];
void dfs(int x)
{
if(x==n)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<g[i][j];
cout<<endl;
}
cout<<endl;
return;
}
for(int i=0;i<n;i++)
{
if(!col[i]&&!dj[x+i]&&!udj[-x+i+n])//利用截距作为数组下标来判断是否有对角线上的棋子存在
{
g[x][i]='Q';
col[i]=dj[x+i]=udj[-x+i+n]=1;
dfs(x+1);
col[i]=dj[x+i]=udj[-x+i+n]=0;
g[x][i]='.';
}
}
return;
}
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;
}
2、搜索方法二
#include <iostream>
using namespace std;
const int N = 10;
int n;
bool row[N], col[N], dg[N * 2], udg[N * 2];
char g[N][N];
void dfs(int x, int y, int s)
{
if (s > n) return;
if (y == n) y = 0, x ++ ;
if (x == n)
{
if (s == n)
{
for (int i = 0; i < n; i ++ ) puts(g[i]);
puts("");
}
return;
}
g[x][y] = '.';
dfs(x, y + 1, s);
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n])
{
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
g[x][y] = 'Q';
dfs(x, y + 1, s + 1);
g[x][y] = '.';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
}
}
int main()
{
cin >> n;
dfs(0, 0, 0);
return 0;
}
BFS(宽度优先搜索)
算法思想
BFS是一层一层地进行搜索的，BFS搜到的点距离起点越来越远。通过BFS可以搜到最短路，第一次搜到的
点即为最短路
代码模板
例子
example 1 : 走迷宫
给定一个
n
×
m
n×m
n
×
m
的二维整数数组，用来表示一个迷宫，数组中只包含
0
0
0
或
1
1
1
，其中
0
0
0
表示可以走的路，
1
1
1
表示不可通过的墙壁。
最初，有一个人位于左上角
(
1
,
1
)
(1,1)
(
1
,
1
)
处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问，该人从左上角移动至右下角
(
n
,
m
)
(n,m)
(
n
,
m
)
处，至少需要移动多少次。
数据保证
(
1
,
1
)
(1,1)
(
1
,
1
)
处和
(
n
,
m
)
(n,m)
(
n
,
m
)
处的数字为
0
0
0
，且一定至少存在一条通路。
#include <cstring>
#include <iostream>
#include <algorithm>
#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;
memset(d, -1, sizeof d);
d[0][0] = 0;
q.push({0, 0});
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
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;
}
树和图的存储
树是一种特殊的图（无环连通图），与图的存储方式相同。
对于无向图中的边
a
,
b
a,b
a
,
b
，存储两条有向边
a
−
>
b
a->b
a
−
>
b
,
b
−
>
a
b->a
b
−
>
a
。
因此我们可以只考虑有向图的存储。
存储方式
-
邻接矩阵
g[
a
]
[
b
]
g[a][b]
g
[
a
]
[
b
]
存储边
a−
>
b
a->b
a
−
>
b
，但这种存储方式浪费了较多的空间，适合用来存储较为稠密的树或图 -
邻接表
在数组中存储每一个点的首地址，后续节点存储与该点相连的点
核心：用数组模拟单链表
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
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);
树与图的遍历
时间复杂度
O
(
n
+
m
)
O(n+m)
O
(
n
+
m
)
,
n
n
n
表示点数，
m
m
m
表示边数
深度优先遍历(DFS)
代码模板
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j]) dfs(j);
}
}
宽度优先遍历(BFS)
代码模板
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
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; // 表示点j已经被遍历过
q.push(j);
}
}
}
例子
example 1 : 树的重心
给定一颗树，树中包含
n
n
n
个结点（编号
1
∼
n
1∼n
1
∼
n
）和
n
−
1
n−1
n
−
1
条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, M = N * 2;
int n;
int h[N], e[M], ne[M], idx;
int ans = N;
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);
size = max(size, s);
sum += s;
}
size = max(size, n - sum - 1);
ans = min(ans, size);
return sum + 1;
}
int main()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs(1);
printf("%d\n", ans);
return 0;
}
example 2 : 图中点的层次
给定一个
n
n
n
个点
m
m
m
条边的有向图，图中可能存在重边和自环。
所有边的长度都是
1
1
1
，点的编号为
1
∼
n
1∼n
1
∼
n
。
请你求出
1
1
1
号点到
n
n
n
号点的最短距离，如果从
1
1
1
号点无法走到
n
n
n
号点，输出
−
1
−1
−
1
。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int bfs()
{
memset(d, -1, sizeof d);
queue<int> q;
d[1] = 0;
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 (d[j] == -1)
{
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
cout << bfs() << endl;
return 0;
}
拓扑排序
算法思想
主要针对的是有向无环图，是对BFS的一大应用。有向无环图一定存在拓扑序列。每次检测是否存在入度为
0
0
0
的点，入度为 $ 0 $ 点即为起点，将其入队，再进行BFS即可。
代码模板
时间复杂度 O(n+m)O(n+m), nn 表示点数，mm 表示边数
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入
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)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}
例子
example 1 : 有向图的拓扑排序
给定一个
n
n
n
个点
m
m
m
条边的有向图，点的编号是
1
1
1
到
n
n
n
，图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出
−
1
−1
−
1
。
若一个由图中所有点构成的序列
A
A
A
满足：对于图中的每条边
(
x
,
y
)
(x,y)
(
x
,
y
)
，
x
x
x
在
A
A
A
中都出现在
y
y
y
之前，则
称
A
A
A
是该图的一个拓扑序列。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
int q[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)
q[ ++ tt] = j;
}
}
return tt == n - 1;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
d[b] ++ ;
}
if (!topsort()) puts("-1");
else
{
for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
puts("");
}
return 0;
}
最短路问题
算法内容
最短路问题一共有两大类，一类是单源最短路问题（一个点到其他所有点），另一类是多源汇最短路问题（起点和终点都不确定）。对于单源最短路问题，又可分为两类。一类是所有的边都是正数的情况，通常使用朴素的dijkstra算法或使用堆优化的dijkstra算法解决。另一类即是存在负权边的情况，通常使用bellman-ford算法或spfa算法来解决。而对于多源汇最短路问题，则使用floyd算法解决。
算法模板
朴素dijkstra算法
时间复杂度是
O
(
n
2
+
m
)
O(n^2+m)
O
(
n
2
+
m
)
,
n
n
n
表示点数，
m
m
m
表示边数
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
堆优化版dijkstra
时间复杂度
O
(
m
l
o
g
n
)
O(mlogn)
O
(
m
l
o
g
n
)
,
n
n
n
表示点数，
m
m
m
表示边数
对于稀疏图需要进行优化
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1}); // first存储距离，second存储节点编号
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;
return dist[n];
}
bellman-ford算法
时间复杂度
O
(
n
⋅
m
)
O(n·m)
O
(
n
⋅
m
)
,
n
n
n
表示点数，
m
m
m
表示边数
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离
struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{
int a, b, w;
}edges[M];
// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。
for (int i = 0; i < n; i ++ )
{
for (int j = 0; j < m; j ++ )
{
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > dist[a] + w)
dist[b] = dist[a] + w;
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n];
}
spfa算法（队列优化的bellman-ford算法）
时间复杂度 平均情况下
O
(
m
)
O(m)
O
(
m
)
，最坏情况下
O
(
n
⋅
m
)
O(n·m)
O
(
n
⋅
m
)
,
n
n
n
表示点数，
m
m
m
表示边数
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
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];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入
{
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
floyd算法
时间复杂度是
O
(
n
3
)
O(n^3)
O
(
n
3
)
,
n
n
n
表示点数
初始化：
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;
// 算法结束后，d[a][b]表示a到b的最短距离
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]);
}
例子
example 1 : Dijkstra求最短路 I
给定一个
n
n
n
个点
m
m
m
条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出
1
1
1
号点到
n
n
n
号点的最短距离，如果无法从
1
1
1
号点走到
n
n
n
号点，则输出
−
1
−1
−
1
。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
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] = min(g[a][b], c);
}
printf("%d\n", dijkstra());
return 0;
}
example 2 : Dijkstra求最短路 II
给定一个
n
n
n
个点
m
m
m
条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出
1
1
1
号点到
n
n
n
号点的最短距离，如果无法从
1
1
1
号点走到
n
n
n
号点，则输出
−
1
−1
−
1
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
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 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] > 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()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}
example 3 : 有边数限制的最短路
给定一个
n
n
n
个点
m
m
m
条边的有向图，图中可能存在重边和自环，
边权可能为负数
。
请你求出从
1
1
1
号点到
n
n
n
号点的最多经过
k
k
k
条边的最短距离，如果无法从
1
1
1
号点走到
n
n
n
号点，输出
impossible
。
注意：图中可能
存在负权回路
。
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, M = 10010;
struct Edge
{
int a, b, c;
}edges[M];
int n, m, k;
int dist[N];
int last[N];
void bellman_ford()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i ++ )
{
memcpy(last, dist, sizeof dist);
for (int j = 0; j < m; j ++ )
{
auto e = edges[j];
dist[e.b] = min(dist[e.b], last[e.a] + e.c);
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edges[i] = {a, b, c};
}
bellman_ford();
if (dist[n] > 0x3f3f3f3f / 2) puts("impossible");
else printf("%d\n", dist[n]);
return 0;
}
example 4 : spfa求最短路
给定一个
n
n
n
个点
m
m
m
条边的有向图，图中可能存在重边和自环，
边权可能为负数
。
请你求出
1
1
1
号点到
n
n
n
号点的最短距离，如果无法从
1
1
1
号点走到
n
n
n
号点，则输出
impossible
。
数据保证不存在负权回路。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
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 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[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;
}
}
}
}
return 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);
add(a, b, c);
}
int t = spfa();
if (t == 0x3f3f3f3f) puts("impossible");
else printf("%d\n", t);
return 0;
}
example 5 : spfa判断负环
给定一个
n
n
n
个点
m
m
m
条边的有向图，图中可能存在重边和自环，
边权可能为负数
。
请你判断图中是否存在负权回路。
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2010, M = 10010;
int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[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 ++ ;
}
bool spfa()
{
queue<int> q;
for (int i = 1; i <= n; i ++ )
{
st[i] = true;
q.push(i);
}
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;
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);
add(a, b, c);
}
if (spfa()) puts("Yes");
else puts("No");
return 0;
}
example 6 : Floyd求最短路
给定一个
n
n
n
个点
m
m
m
条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定
k
k
k
个询问，每个询问包含两个整数
x
x
x
和
y
y
y
，表示查询从点
x
x
x
到点
y
y
y
的最短距离，如果路径不存在，则输出
impossible
。
数据保证图中不存在负权回路。
#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()
{
scanf("%d%d%d", &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 printf("%d\n", t);
}
return 0;
}
最小生成树
代码模板
朴素prim算法
时间复杂度是
O
(
n
2
+
m
)
O(n^2+m)
O
(
n
2
+
m
)
,
n
n
n
表示点数，
m
m
m
表示边数
int n; // n表示点数
int g[N][N]; // 邻接矩阵，存储所有边
int dist[N]; // 存储其他点到当前最小生成树的距离
bool st[N]; // 存储每个点是否已经在生成树中
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
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;
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;
}
Kruskal算法
时间复杂度是
O
(
m
l
o
g
m
)
O(mlogm)
O
(
m
l
o
g
m
)
,
n
n
n
表示点数，
m
m
m
表示边数
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
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 ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
例子
example 1 : Prim算法求最小生成树
给定一个
n
n
n
个点
m
m
m
条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出
impossible
。
给定一张边带权的无向图
G
=
(
V
,
E
)
G=(V,E)
G
=
(
V
,
E
)
，其中
V
V
V
表示图中点的集合，
E
E
E
表示图中边的集合，
n
=
∣
V
∣
n=|V|
n
=
∣
V
∣
，
m
=
∣
E
∣
m=|E|
m
=
∣
E
∣
。
由
V
V
V
中的全部
n
n
n
个顶点和
E
E
E
中
n
−
1
n−1
n
−
1
条边构成的无向连通子图被称为
G
G
G
的一棵生成树，其中边的权值之和最小的生成树被称为无向图
G
G
G
的最小生成树。
#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];
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;
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()
{
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;
}
example 2 : Kruskal算法求最小生成树
给定一个
n
n
n
个点
m
m
m
条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出
impossible
。
给定一张边带权的无向图
G
=
(
V
,
E
)
G=(V,E)
G
=
(
V
,
E
)
，其中
V
V
V
表示图中点的集合，
E
E
E
表示图中边的集合，
n
=
∣
V
∣
n=|V|
n
=
∣
V
∣
，
m
=
∣
E
∣
m=|E|
m
=
∣
E
∣
。
由
V
V
V
中的全部
n
n
n
个顶点和
E
E
E
中
n
−
1
n−1
n
−
1
条边构成的无向连通子图被称为
G
G
G
的一棵生成树，其中边的权值之和最小的生成树被称为无向图
G
G
G
的最小生成树。
#include <cstring>
#include <iostream>
#include <algorithm>
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 &W)const
{
return w < W.w;
}
}edges[M];
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int kruskal()
{
sort(edges, edges + m);
for (int i = 1; i <= n; i ++ ) p[i] = i; // 初始化并查集
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 ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
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};
}
int t = kruskal();
if (t == INF) puts("impossible");
else printf("%d\n", t);
return 0;
}