-
最短路Dijkstra，spfa，图论二分图算法AYIT---ACM训练(模板版)
文章目录
前言
最短路Dijkstra，spfa，图论二分图算法AYIT—ACM训练(模板版)
A — Dijkstra
B — spfa/Dijkstra
C — 二分图
D — 二分图
E — 二分图
F — 二分图
G — Dijkstra
H — Topsort
A - Dijkstra Algorithm
0x00 算法题目
0x01 算法思路
Dijkstra算法基础模板题
💬 模板演示：
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; return 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
0x02 代码实现
朴素版本Dijkstra：
💬 代码演示：
#include#include #include using namespace std; const int N = 510; int g[N][N]; bool st[N]; int dist[N]; int n,s,f; int dijkstra() { memset(dist,0x3f,sizeof dist); dist[s]=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[f]==0x3f3f3f3f) return -1; return dist[f]; } int main() { cin>>n>>s>>f; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int x; cin>>x; if(x==-1) g[i][j]=0x3f3f3f3f; else g[i][j]=x; } } int t =dijkstra(); cout<<t<<endl; return 0; } - 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
- 52
🚩 运行结果：
spfa算法：
💬 代码演示：#include#include #include #include using namespace std; const int N=110,M=110*110; int n,s,f; bool st[N]; int h[N],w[M],ne[M],e[M],idx; int dist[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[s]=0; queue<int> q; q.push(s); 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[f]==0x3f3f3f3f) return -1; else return dist[f]; } int main() { cin>>n>>s>>f; memset(h,-1,sizeof h); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { int x; cin>>x; //if(x==-1) continue; if(x>0) add(i,j,x); } } cout<<spfa()<<endl; return 0; } - 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
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
🚩 运行结果：
B - 最长路
0x00 算法题目
0x01 算法思路
spfa算法基础模板题
💬 模板演示：
int spfa() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; queue<int> q; q.push(1); 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]) { q.push(j); st[j]=true; } } } } return 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
0x02 代码实现
spfa算法：
💬 代码演示：#include#define endl '\n' using namespace std; const int N = 1510,INF = 0x3f3f3f3f; int n,m; int dist[N]; int g[N][N]; queue<int> q; void spfa() { memset(dist,-1,sizeof dist); dist[1]=0; q.push(1); while(!q.empty()) { int t = q.front(); q.pop(); for(int j=1;j<=n;j++) { if(g[t][j] && dist[j] < dist[t] + g[t][j]) { dist[j] = dist[t] + g[t][j]; q.push(j); } } } } int main() { cin>>n>>m; for(int i=1;i<=m;i++) { int a,b,c; cin>>a>>b>>c; g[a][b]=max(g[a][b],c); } spfa(); cout<<dist[n]<<endl; return 0; } - 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
🚩 运行结果：
C - 二分图最大匹配
0x00 算法题目
0x01 算法思路
二分图模板题
💬 模板演示：
//邻接表 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; } //邻接矩阵 bool find(int x) { for(int i=0;i<g[x].size();++i) { int j = g[x][i]; if(!st[j]) { st[j]=true; if(match[j]==0 || find(match[j])) { match[j]=x; return true; } } } return false; }- 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
0x02 代码实现
💬 代码演示：
#include#include using namespace std; const int N = 510,M=5e4+10; int n,m,q; int h[N],e[M],ne[M],idx; int match[N]; bool st[N]; 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() { cin>>n>>m>>q; memset(h,-1,sizeof h); while(q--) { int u,v; cin>>u>>v; add(u,v); } int res=0; for(int i=1;i<=n;i++) { memset(st,false,sizeof st); if(find(i)) res++; } cout<<res<<endl; return 0; } - 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
- 52
- 53
- 54
- 55
🚩 运行结果：
D - 搭配飞行员
0x00 算法题目
0x01 算法思路
二分图模板题
💬 模板演示：
//邻接表 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; } //邻接矩阵 bool find(int x) { for(int i=0;i<g[x].size();++i) { int j = g[x][i]; if(!st[j]) { st[j]=true; if(match[j]==0 || find(match[j])) { match[j]=x; return true; } } } return false; }- 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
0x02 代码实现
💬 代码演示：
#include#include #include #include using namespace std; const int N = 110; int n,m; int map[N][N]; int match[N]; bool st[N]; vector<int> g[N]; bool find(int x) { for(int i=0;i<g[x].size();++i) { int j = g[x][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",&n,&m); int a,b; while(cin>>a>>b) { g[a].push_back(b); } int res = 0; for(int i=1;i<=m;i++) { memset(st,false,sizeof st); if(find(i)) { res++; } } cout<<res; return 0; } - 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
- 52
- 53
- 54
- 55
🚩 运行结果：
E - The Perfect Stall
0x00 算法题目
0x01 算法思路
二分图模板题
💬 模板演示：
//邻接表 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; } //邻接矩阵 bool find(int x) { for(int i=0;i<g[x].size();++i) { int j = g[x][i]; if(!st[j]) { st[j]=true; if(match[j]==0 || find(match[j])) { match[j]=x; return true; } } } return false; }- 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
0x02 代码实现
💬 代码演示：
#include#include using namespace std; const int N = 510,M=5e4+10; int n,m; int match[N]; bool st[N]; vector<int> g[N]; bool find(int x) { for(int i=0;i<g[x].size();++i) { int j = g[x][i]; if(!st[j]) { st[j]=true; if(match[j]==0 || find(match[j])) { match[j]=x; return true; } } } return false; } int main() { while(~scanf("%d%d",&n,&m)) { memset(st,false,sizeof st); memset(match,0,sizeof match); for(int i=1;i<=n;i++) { g[i].clear(); int s; cin>>s; while(s--) { int q; cin>>q; g[i].push_back(q); } } int res=0; for(int i=1;i<=n;i++) { memset(st,false,sizeof st); if(find(i)) res++; } cout<<res<<endl; } return 0; } - 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
- 52
- 53
- 54
- 55
- 56
- 57
🚩 运行结果：
F - Asteroids
0x00 算法题目
0x01 算法思路
二分图模板题
💬 模板演示：
//邻接表 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; } //邻接矩阵 bool find(int x) { for(int i=0;i<g[x].size();++i) { int j = g[x][i]; if(!st[j]) { st[j]=true; if(match[j]==0 || find(match[j])) { match[j]=x; return true; } } } return false; }- 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
0x02 代码实现
💬 代码演示：
#include#include using namespace std; const int N = 510,M=5e4+10; int n,m,q; int h[N],e[M],ne[M],idx; int match[N]; bool st[N]; 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() { cin>>n>>m; memset(h,-1,sizeof h); while(m--) { int u,v; cin>>u>>v; add(u,v); } int res=0; for(int i=1;i<=n;i++) { memset(st,false,sizeof st); if(find(i)) res++; } cout<<res<<endl; return 0; } - 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
- 52
- 53
🚩 运行结果：
G - Til the Cows Come Home
0x00 算法题目
0x01 算法思路
Dijkstra算法基础模板题
💬 模板演示：
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; return 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
0x02 代码实现
💬 代码演示：
#include#include #include #include using namespace std; const int N=1010,inf = 0x3f3f3f3f; int n,m; bool st[N]; int dist[N]; int g[N][N]; int dijkstra() { memset(dist,inf,sizeof(dist)); dist[1]= 0; for(int i=1;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]); } return dist[n]; } int main() { cin>>m>>n; memset(g,inf,sizeof g); for(int i=0;i<m;++i) { int a,b,c; cin>>a>>b>>c; g[a][b]=g[b][a]=min(g[a][b],c); } cout<< dijkstra() <<endl; return 0; } - 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
🚩 运行结果：
H - 拓扑排序
0x00 算法题目
0x01 算法思路
拓扑排序算法基础模板题
💬 模板演示：
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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
0x02 代码实现
💬 代码演示：
#include#include #include #include #include using namespace std; const int N=100010; int n,m; vector<int> v[N]; int size,d[N]; int ans[N]; void topsort() { priority_queue<int,vector<int>,greater<int> > q; for(int i=1;i<=n;i++) if(!d[i]) q.push(i); while(!q.empty()) { int t = q.top(); q.pop(); ans[size++] = t; for(auto it : v[t]) { d[it]--; if(!d[it]) q.push(it); } } } int main() { cin>>n>>m; for(int i=0;i<m;i++) { int a,b; cin>>a>>b; v[a].push_back(b); d[b]++; } topsort(); for(int i=0 ; i<size ;i++) cout<< 'v' << ans[i] <<' '; return 0; } - 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
- 52
- 53
🚩 运行结果：
总结
这次训练很明显涉及到了最短路Dijkstra，spfa，图论二分图算法，以及topsort算法，这次考的比较基础，但是让我意识到了，算法必须熟练记忆模板是很重要的。
-
相关阅读:
[golang 流媒体在线直播系统] 2.搭建基于golang的流媒体服务器实现拉流推流,以及Html客户端拉取hls类型的流
聊聊动效降级
【Flutter】支持多平台 多端保存图片到本地相册 (兼容 Web端 移动端 android 保存到本地)
LeetCode每日温度
flink技术总结待续
16 用于NOMA IoT网络上行链路安全速率最大化的HAP和UAV协作框架
JVM的GC算法CMS和G1
2023最新SSM计算机毕业设计选题大全（附源码+LW）之java高校饭堂管理系统8gmjo
Open3D读取文件
十、网络编程之 poll 详解.md
- 原文地址：https://blog.csdn.net/congfen214/article/details/132654612
