我是靠谱客的博主 时尚篮球，这篇文章主要介绍北京化工大学数据结构2022/11/24作业 题解问题 A: 图的最小生成树-Prim算法问题 B: 图的最小生成树-Kruskal算法问题 C: 算法7-9：最小生成树问题 D: 算法7-15：迪杰斯特拉最短路径算法问题 E: 算法7-16：弗洛伊德最短路径算法问题 F: 图的最短路径-Floyd算法输出最短路径包含的边，现在分享给大家，希望可以做个参考。
后天要去最后一场区域赛了，文字先鸽
打完润了
目录
问题 A: 图的最小生成树-Prim算法
问题 B: 图的最小生成树-Kruskal算法
问题 C: 算法7-9：最小生成树
问题 D: 算法7-15：迪杰斯特拉最短路径算法
问题 E: 算法7-16：弗洛伊德最短路径算法
问题 F: 图的最短路径-Floyd算法输出最短路径包含的边
问题 A: 图的最小生成树-Prim算法
复制代码
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#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N = 110; int arr[100][100]; int cost[N],adj[N]; signed main(){ int n; cin>>n; fer(i,0,n-1){ fer(j,0,n-1){ cin>>arr[i][j]; } } fer(i,0,n-1){ if(arr[0][i]!=0){ cout<<i<<" "<<arr[0][i]<<" "<<"0"<<'n'; } else{ cout<<i<<" - -"<<'n'; } } }
问题 B: 图的最小生成树-Kruskal算法
这题非要这咱手写排序
巨**
复制代码
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#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N=1000,M=N*2; struct edg { int arc,ver,c; }; signed main() { int n; cin>>n; vector<edg> g; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { int x; cin>>x; if(x) { g.push_back({i,j,x}); } } } for(int i=0;i<g.size();i++) { for(int j=i+1;j<g.size();j++) { if(g[i].c>g[j].c) { swap(g[i],g[j]); } } } for(int i=0;i<g.size();i++){ cout<<"<"<<g[i].arc<<","<<g[i].ver<<">"<<":"<<g[i].c<<'n'; } }
问题 C: 算法7-9：最小生成树
kruskal板子
复制代码
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
67
68
69#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N=1000,M=N*2; int p[N]; const int INF=1000000007; 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 n,m; 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; } signed main(){ cin>>n; fer(i,1,n){ fer(j,1,n){ int xx; cin>>xx; if(xx){ edges[m]={i,j,xx}; m++; } } } cout<<kruskal(); }
问题 D: 算法7-15：迪杰斯特拉最短路径算法
复制代码
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#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} const int N=1000,inf=0x3f3f3f3f; int w[N][N]; int dist[N]; int vis[N]; void dijistra(int n,int be){ memset(dist,0x3f,sizeof dist); vis[be]=1; dist[be]=0; int now=be; for(int i=0;i<n-1;i++){ for( int j=0;j<n;j++){ if(w[now][j]==0||vis[j]==1) continue; dist[j]=min(dist[j],dist[now]+w[now][j]); } int ne=0,minn=inf; for( int j=0;j<n;j++){ if(vis[j]==1) continue; if(dist[j]<minn){ minn=dist[j]; ne=j; } } now=ne; vis[ne]=1; } return ; } signed main(){ int n; int be; input(n,be); fer(i,0,n-1){ fer(j,0,n-1){ input(w[i][j]); } } dijistra(n,be); for(int i=0;i<n;i++){ if(i==be){ continue; } else{ cout<<dist[i]<<" "; } } }
问题 E: 算法7-16：弗洛伊德最短路径算法
复制代码
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 <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} int mat[500][500]; int dis[500][500]; signed main(){ int n; cin>>n; memset(dis,0x3f,sizeof dis); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ input(mat[i][j]); if(mat[i][j]!=0) dis[i][j]=mat[i][j]; } } for(int i=0;i<n;i++) dis[i][i]=0; for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j]; } } } for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cout<<dis[i][j]<<" "; } cout<<'n'; } }
问题 F: 图的最短路径-Floyd算法输出最短路径包含的边
复制代码
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#include <bits/stdc++.h> #define int long long #define pb push_back #define fer(i,a,b) for(int i=a;i<=b;++i) #define der(i,a,b) for(int i=a;i>=b;--i) #define all(x) (x).begin(),(x).end() #define pll pair<int,int> #define et cout<<'n' #define xx first #define yy second using namespace std; template <typename _Tp>void input(_Tp &x){ char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar(); x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar(); if(f)x=-x; } template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);} int dij[101][101]; int path[101][101]; int a[101][101]; signed main(){ int n; input(n); fer(i,0,n-1) fer(j,0,n-1){ int x,y; input(x,y); if(x!=-1){ dij[i][j] = x; path[i][j] = y; } } int x,y; input(x,y); int p = path[x][y]; stack<int>s; s.push(y); while (p!=x) { s.push(p); p = path[x][p]; } s.push(x); cout<<dij[x][y]<<'n'; while(s.size()){ auto t=s.top(); cout<<t<<" "; s.pop(); } }
最后
以上就是时尚篮球最近收集整理的关于北京化工大学数据结构2022/11/24作业 题解问题 A: 图的最小生成树-Prim算法问题 B: 图的最小生成树-Kruskal算法问题 C: 算法7-9：最小生成树问题 D: 算法7-15：迪杰斯特拉最短路径算法问题 E: 算法7-16：弗洛伊德最短路径算法问题 F: 图的最短路径-Floyd算法输出最短路径包含的边的全部内容，更多相关北京化工大学数据结构2022/11/24作业内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复