求点之间距离不相同的最短路算法
时间复杂度$O(n^2+m)$,n表示点数,m表示边数,模板题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
int g[N][N]; // 存储图
int dist[N]; // 1号点到每个点的距离
int st[N]; // 是否已经确定为最小距离
int n,m; // 点数 边数
int dijkstra(){
// 初始化距离
memset(dist,0x3f,sizeof(dist));
dist[1] = 0;
for(int i = 0; i < n - 1; i++){
// 找到没有在集合st中，距离起点最近的点
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中
st[t] = true;
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
typedef pair<int,int> PII;
priority_queue< PII,vector<PII>,greater<PII> > heap;
const int N = 1e5 + 10;
vector<PII> g[N];
int dist[N]; // 1号点到每个点的距离
int st[N]; // 是否已经确定为最小距离
int n,m; // 点数 边数
int dijkstra(){
// 初始化距离
memset(dist,0x3f,sizeof(dist));
dist[1] = 0;
heap.push({0, 1});
for(int i = 1; i < n; i++){
// 找到没有在集合st中，距离起点最近的点
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
// 将该点加入st中
if(st[ver]) continue;
st[ver] = true;
// 更新距离
for(auto to : g[ver]){
int dis = to.first, tar = to.second;
if(dist[tar] > dist[ver] + dis){
dist[tar] = dist[ver] + dis;
heap.push({dist[tar],tar});
}
}
}
return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
}
int main(){
cin >> n >> m;
while(m--){
int a,b,c;
cin >> a >> b >> c;
// g[a][b] = min(g[a][b],c);
// 先是距离，后是点
g[a].push_back({c,b});
}
cout << dijkstra();
return 0;
}
|
DAG: 有向无环图
拓扑序形象理解: 一些敌人可以互相看到，你要暗杀所有人而不被发现
模板题链接: https://acwing.com/problem/content/description/850/
伪代码:
把所有入度为零的点，扔到一个队列里:
while 队列非空:
取队首点P
访问P的所有相邻点O，将其入度减一
若此时入度为0,Q入队
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5+10;
int deg[N];
vector<int> v[N];
queue<int> q;
int n,m;
vector<int> topsort(){
vector<int> ans;
for(int i = 1; i <= n; i++)
if(deg[i] == 0) q.push(i);
while(q.size()){
int now = q.front();
ans.push_back(now);
q.pop();
for(auto to: v[now]){
deg[to] -= 1;
if(deg[to] == 0)
q.push(to);
}
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin >> n >> m;
while(m--){
int x,y;
cin >> x >> y;
v[x].push_back(y);
deg[y]++;
}
auto res = topsort();
if(res.size() == n)
for(auto x: res) cout << x << " ";
else
cout << -1 << endl;
return 0;
}
|
求图中的带有负边的最短路算法
n表示点数,m表示边数
最好时间复杂度$O(m)$,最好时间复杂度$O(nm)$,模板题
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n,m;
typedef pair<int,int> PII;
vector<PII> g[N];
int st[N];
int dist[N];
int spfa(){
memset(dist,0x3f,sizeof dist);
queue<int> q;
q.push(1);
st[1] = true;
dist[1] = 0;
while(q.size()){
int front = q.front();
q.pop();
st[front] = false;
for(auto to : g[front]){
int t = to.first;
int w = to.second;
if(dist[t] > dist[front] + w){
dist[t] = dist[front] + w;
if( !st[t] ) {
st[t] = true;
q.push(t);
}
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
ios::sync_with_stdio(0);
cin >> n >> m;
while(m--){
int u,v,w;
cin >> u >> v >> w;
g[u].push_back({v,w});
}
int res = spfa();
if(res == -1) cout << "impossible" << endl;
else cout << res << endl;
return 0;
}
求图中的最小生成树算法
时间复杂度$O(n^2+m)$,n表示点数,m表示边数,模板题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
const int N = 550, INF = 0x3f3f3f3f;
int g[N][N], st[N], dist[N];
int n,m;
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;
}
|
求图中的强联通分量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
int dfn[N], low[N]; // 高低数组
int stk[N], top, ts; // 模拟栈
bool in_stk[N]; // 是否在栈中
void tarjan(int now){
// 0. 准备遍历now这个点
dfn[now] = low[now] = ++ ts;
stk[++top] = now, in_stk[now] = true;
for(int to:v[now]){
// 1. 看看下一个点是否能更新当前点的时间戳
if(!dfn[to]){
tarjan(to);
low[now] = min(low[now],low[to]);
}
// 2. 下一个点在栈中，看看能否更新当前点的时间戳
else if(in_stk[to]) low[now] = min(low[now],low[to]);
}
// 3. 将当前节点进行出栈
if(dfn[now] == low[now]){
int y,cnt = 0;
do{
y = stk[top --];
in_stk[y] = false;
}while(y != now);
}
}
|