实验10 拓扑排序与最短路径2022

news/2024/11/23 4:01:10/

A. DS图—图的最短路径（无框架）

题目描述

给出一个图的邻接矩阵，输入顶点v，用迪杰斯特拉算法求顶点v到其它顶点的最短路径。

输入

第一行输入t，表示有t个测试实例

第二行输入顶点数n和n个顶点信息

第三行起，每行输入邻接矩阵的一行，以此类推输入n行

第i个结点与其它结点如果相连则为距离，无连接则为0，数据之间用空格隔开。

第四行输入一个顶点v，表示求该顶点v到其他顶点的最短路径距离

以此类推输入下一个示例

输出

对每组测试数据，输出：

每行输出顶点v到某个顶点的最短距离和最短路径

每行格式：顶点v编号-其他顶点编号-最短路径值----[最短路径]。没有路径输出：顶点v编号-其他顶点编号--1。具体请参考示范数据

输入：

2
5 0 1 2 3 4
0 5 0 7 15
0 0 5 0 0
0 0 0 0 1
0 0 2 0 0
0 0 0 0 0
0
6 V0 V1 V2 V3 V4 V5
0 0 10 0 30 100
0 0 5 0 0 0
0 0 0 50 0 0
0 0 0 0 0 10
0 0 0 20 0 60
0 0 0 0 0 0
V0
0-1-5----[0 1 ]
0-2-9----[0 3 2 ]
0-3-7----[0 3 ]
0-4-10----[0 3 2 4 ]
V0-V1--1
V0-V2-10----[V0 V2 ]
V0-V3-50----[V0 V4 V3 ]
V0-V4-30----[V0 V4 ]
V0-V5-60----[V0 V4 V3 V5 ]

代码：

#include <iostream>
using namespace std;
#define INF 9999999
class graph {int vertex_num;string* vertex;//存储顶点int** edge;//存储矩阵边之间的长度bool* visited;string** path;//路径int* dest;//开始顶点到其它顶点的距离string startString;//开始顶点
public:graph() {}graph(int num, string* a, int** b, string start);void Dijkstra();void display();void show();
};void graph::show() {cout << "***************************" << endl;for (int i = 0; i < vertex_num; i++) {for (int j = 0; j < vertex_num; j++) cout << path[i][j];cout << endl;}
}
graph::graph(int num, string* a, int** b, string start) {vertex_num = num;startString = start;vertex = new string[vertex_num];edge = new int* [vertex_num];visited = new bool[vertex_num];dest = new int[vertex_num];path = new string * [vertex_num];for (int i = 0; i < vertex_num; i++) {visited[i] = false;vertex[i] = a[i];path[i] = new string[vertex_num];edge[i] = new int[vertex_num];for (int j = 0; j < vertex_num; j++) {edge[i][j] = b[i][j];path[i][j] ="";}}
}void graph::Dijkstra() {int start;for (int i = 0; i < vertex_num; i++) {if (vertex[i] == startString) {start = i;path[start][0] = "";break;}}for (int i = 0; i < vertex_num; i++) {if ((i != start) || edge[i] == 0) {dest[i] = INF;if ((edge[start][i] < INF) && edge[start][i] != 0) {dest[i] = edge[start][i];path[i][0] = vertex[start];path[i][1] = vertex[i];path[i][2] = "";}}}dest[start] = 0;visited[start] = true;int mindest = INF, currentVex = 0;for (int i = 0; i < vertex_num; i++) {mindest = INF;for (int j = 0; j < vertex_num; j++) {if (visited[j] == false) {if (dest[j] < mindest) {currentVex = j;mindest = dest[j];}}}int count = 0;visited[currentVex] = true;for (int j = 0; j < vertex_num; j++) {if ((visited[j] == false) && (mindest + edge[currentVex][j] < dest[j])) {dest[j] = mindest + edge[currentVex][j];for (count = 0; path[currentVex][count] != ""; count++)path[j][count] = path[currentVex][count];path[j][count++] = vertex[j];path[j][count] = "";}}}
}void graph::display() {int index;for (int i = 0; i < vertex_num; i++) if (vertex[i] == startString) index = i;for (int i = 0; i < vertex_num; i++) {if (vertex[i] != startString) {if (dest[i] ==INF) cout << startString << "-" << vertex[i] << "--1" << endl;else {cout << startString << "-" << vertex[i] << "-" <<dest[i] << "----[";for (int j = 0; path[i][j] != ""; j++) cout << path[i][j] << " ";cout << "]" << endl;}}}
}int main() {int t;cin >> t;while (t--) {int vertex_num;string* vertex, startString;int** edge;cin >> vertex_num;vertex = new string[vertex_num];edge = new int* [vertex_num];for (int i = 0; i < vertex_num; i++) {edge[i] = new int[vertex_num];cin >> vertex[i];}for (int i = 0; i < vertex_num; i++)for (int j = 0; j < vertex_num; j++) {cin >> edge[i][j];if (edge[i][j] == 0) edge[i][j] = INF;}cin >> startString;graph gp(vertex_num, vertex, edge, startString);int s = 0;gp.Dijkstra();gp.display();}
}

B. 图综合练习--拓扑排序

题目描述

已知有向图，顶点从0开始编号，求它的求拓扑有序序列。

拓扑排序算法：给出有向图邻接矩阵

1.逐列扫描矩阵，找出入度为0且编号最小的顶点v

2.输出v，并标识v已访问

3.把矩阵第v行全清0

重复上述步骤，直到所有顶点输出为止

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入

第一行输入一个整数t，表示有t个有向图

第二行输入n，表示图有n个顶点

第三行起，输入n行整数，表示图对应的邻接矩阵

以此类推输入下一个图的顶点数和邻接矩阵

输出

每行输出一个图的拓扑有序序列

输入：

2
5
0 1 0 1 1
0 0 1 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 0 0
7
0 0 0 0 0 0 0
1 0 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 1 0

输出：

0 1 3 2 4 
4 6 5 1 3 2 0

代码：

#include <iostream>
using namespace std;class Graph{int vexNum;int **matrix;bool *visit;int inDegreeZero();
public:Graph();~Graph();void TopSort();
};Graph::Graph() {cin>>vexNum;matrix = new int*[vexNum];visit = new bool[vexNum];for(int i=0;i<vexNum;i++){visit[i] = false;matrix[i] = new int[vexNum];for(int j=0;j<vexNum;j++)cin>>matrix[i][j];}
}Graph::~Graph() {delete visit;for(int i=0;i<vexNum;i++)delete []matrix[i];delete []matrix;
}void Graph::TopSort() {for(int k=0;k<vexNum;k++){int v=inDegreeZero();cout<<v<<' ';visit[v] = true;for(int i=0;i<vexNum;i++)matrix[v][i]=0;}cout<<endl;
}int Graph::inDegreeZero() {for(int col=0;col<vexNum;col++){bool flag= true;for(int row=0;row<vexNum;row++){if(matrix[row][col]!=0)flag= false;}if(flag && !visit[col])return col;}return -1;
}int main()
{int t;cin>>t;while (t--){Graph myGraph;myGraph.TopSort();}return 0;
}

E. 拯救007

题目描述

在老电影“007之生死关头”（Live and Let Die）中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）

设鳄鱼池是长宽为100米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要告诉他是否有可能逃出生天。

输入

首先第一行给出两个正整数：鳄鱼数量 N（≤100）和007一次能跳跃的最大距离 D。随后 N 行，每行给出一条鳄鱼的 (x,y) 坐标。注意：不会有两条鳄鱼待在同一个点上。

输出

如果007有可能逃脱，就在一行中输出"Yes"，否则输出"No"。

输入：

14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12

输出：

Yes

代码：

#include<iostream>
#include<math.h>
using namespace std;double x[200], y[200], vis[200];
double n, m, flag = 0;int DFS(int x1, int y1)
{if (abs(abs(x1) - 50) <= m || abs(abs(y1) - 50) <= m)//其绝对值小于mreturn flag = 1;for (int i = 0; i < n; i++){if (!vis[i] && pow(x1 - x[i], 2) + pow(y1 - y[i], 2) <= m * m)vis[i] = 1, DFS(x[i], y[i]), vis[i] = 0;}return 0;
}int main()
{cin >> n >> m;for (int i = 0; i < n; i++)cin >> x[i] >> y[i];if (m + 7.5 >= 50) flag = 1;for (int i = 0; i < n; i++){if (pow(x[i], 2) + pow(y[i], 2) <= (m + 7.5) * (m + 7.5)){vis[i] = 1;DFS(x[i], y[i]);vis[i] = 0;}}if (flag) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

F. 货币套汇（图路径）

题目描述

套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，1法郎可以买到0.16美元。通过货币兑换，一个商人可以从1 美元开始买入，得到0.7×9.5×0.16=1.064美元，从而获得6.4%的利润。 给定n种货币c1 ,c2 ,... ,cn的有关兑换率，试设计一个有效算法，确定货币间是否存在套汇的可能性。

提示：判断图上是否出现正环,即环上所有的边相乘大于1

输入

第一行：测试数据组数

每组测试数据格式为：

第一行：正整数n (1< =n< =30)，正整数m，分别表示n种货币和m种不同的货币兑换率。

2~n+1行，n种货币的名称。

n+2~n+m+1行，每行有3 个数据项ci，rij 和cj ，表示货币ci 和cj的兑换率为 rij。

输出

对每组测试数据，如果存在套汇的可能则输出YES

如果不存在套汇的可能，则输出NO。

输入：

2
3 3
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3 6
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

输出：

YES
NO

代码：

#include <iostream>
#include<string>
using namespace std;#define MAX_NUM 20class AdjMatrix
{
private:double matrix[MAX_NUM][MAX_NUM];string vex[MAX_NUM];//顶点表int NodeNum;int ArcNum;int conn_num;double value; ///路径汇率乘积int flag; ///是否能套汇int Visit[MAX_NUM];void DFS(int v){int w, i, k;if (Visit[v] == 0)Visit[v] = 1;int* AdjVex = new int[NodeNum];for (i = 0; i < NodeNum; i++)AdjVex[i] = -1;k = 0; ///寻找其相邻的点for (i = 0; i < NodeNum; i++){if (matrix[v][i] != 0) {AdjVex[k] = i;k++;}}i = 0;for (w = AdjVex[0]; w != -1; w = AdjVex[i]){ ///访问其所有相邻的点if (Visit[w] == 0){value = value * matrix[v][w];DFS(w);}else if (Visit[w] == 2) //如果可以回到初始点形成环{double TempValue = value; //判定边乘积是否大于1TempValue = TempValue * matrix[v][w];if (TempValue > 1.0){flag = 1;}}i++;}delete[]AdjVex;}public:AdjMatrix(int n){NodeNum = n;conn_num = 0;flag = 0;}~AdjMatrix() {}int Index(string s){for (int i = 0; i < NodeNum; i++){if (vex[i] == s)return i;}return -1;}void getMatrix(){for (int i = 0; i < NodeNum; i++)for (int j = 0; j < NodeNum; j++)matrix[i][j] = 0;//初始化矩阵cin >> ArcNum;for (int i = 0; i < NodeNum; i++){string s1;cin >> s1;vex[i] = s1;}for (int i = 0; i < ArcNum; i++){string s1, s2;double currency;int num1, num2;cin >> s1;cin >> currency;cin >> s2;num1 = Index(s1);num2 = Index(s2);matrix[num1][num2] = currency;}}void print(){int i, j;for (i = 0; i < NodeNum; i++){ ///输出点cout << vex[i];if (i != NodeNum - 1)cout << "\t";}cout << endl;for (i = 0; i < NodeNum; i++){for (j = 0; j < NodeNum; j++){cout << matrix[i][j];if (j != NodeNum - 1)cout << "\t";}cout << endl;}}void DFS(){int v, k;int i;for (k = 0; k < NodeNum; k++){int counter = 0;value = 1.0;v = k;for (i = 0; i < NodeNum; i++){if (i == v)Visit[i] = 2; ///表示起始点elseVisit[i] = 0;}do{if (Visit[v] == 0 || Visit[v] == 2){counter++;if (counter > 1) break; //表示从该点出发无法形成环，直接跳过DFS(v);}v = (v + 1) % NodeNum;} while (v != k);}if (flag == 1)cout << "YES";elsecout << "NO";cout << endl;}
};int main()
{int t;cin >> t;while (t--){int n;cin >> n;AdjMatrix mymatrix(n);mymatrix.getMatrix();mymatrix.DFS();}return 0;
}

http://www.ppmy.cn/news/26008.html

相关文章

杭州电子科技大学2023年MBA招生考试成绩查询和复查申请的通知

杭州电子科技大学2023年MBA招生考试成绩查询和复查申请的通知

根据往年的情况&#xff0c;2023杭州电子大学MBA考试初试成绩可能将于2月21日公布&#xff0c;最早于20号出来&#xff0c;为了广大考生可以及时查询到自己的分数&#xff0c;杭州达立易考教育为大家汇总了信息。根据教育部和浙江省教育考试院关于硕士研究生招生考试工作的统一…
阅读更多...
JVM详解——类的加载

JVM详解——类的加载

文章目录类的加载1、Java程序如何运行2、Java字节码文件3、类加载4、类加载的过程5、类加载器6、类的加载方式7、类的加载机制8、双亲委派机制9、破坏双亲委派机制类的加载 1、Java程序如何运行 首先通过Javac命令将.java文件编译生成.class字节码文件。 Javac是Java编译命令&a…
阅读更多...
机试_3_数据结构（一）_习题

机试_3_数据结构（一）_习题

数据结构&#xff08;一&#xff09;——练习题 学习完第三章-数据结构&#xff08;一&#xff09;之后&#xff0c;当然要做相应地练习啦~ 注&#xff1a;上述习题都可以在牛客进行测试。 例如&#xff0c;第2题链接&#xff1a;计算表达式_牛客题霸_牛客网 (nowcoder.com)…
阅读更多...
剑指 Offer 53 - II. 0～n-1中缺失的数字

剑指 Offer 53 - II. 0～n-1中缺失的数字

摘要 剑指 Offer 53 - II. 0&#xff5e;n-1中缺失的数字 一个长度为n-1的递增排序数组中的所有数字都是唯一的&#xff0c;并且每个数字都在范围0&#xff5e;n-1之内。在范围0&#xff5e;n-1内的n个数字中有且只有一个数字不在该数组中&#xff0c;请找出这个数字。 一、…
阅读更多...
51单片机最强模块化封装(5)

51单片机最强模块化封装(5)

文章目录 前言一、创建timer文件，添加timer文件路径二、timer文件编写三、模块化测试总结前言 今天这篇文章将为大家封装定时器模块，定时器是工程项目中必不可少的，希望大家能够将定时器理解清楚并且运用自如。 一、创建timer文件，添加timer文件路径 这里的操作就不过多…
阅读更多...
【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波

【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波

【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波 文章目录【图神经网络】图拉普拉斯滤波器如何实现全通、低通、高通滤波1. 前言2. 符号说明3. 三种滤波3.1 全通滤波3.2 低通滤波3.2.1 平滑信号分析3.2.2 广义拉普拉斯平滑滤波器3.3 高通滤波4. 总结1. 前言 GCN&…
阅读更多...
贴吧手机端防删图GIF动态图制作解析

贴吧手机端防删图GIF动态图制作解析

贴吧存活 思路技术运气 1&#xff1a;防删图不是存活的绝对因素&#xff0c;除了防删图&#xff0c;还有账号&#xff0c;ip&#xff0c;内容&#xff0c;吧的问题 2&#xff1a;一个图不是每个吧都可以发 3&#xff1a;一个贴不被删不仅仅看图片 4&#xff1a;有时候运气也很…
阅读更多...
[Android Studio] Android Studio Virtual Device（AVD）虚拟机的功能试用

[Android Studio] Android Studio Virtual Device（AVD）虚拟机的功能试用

&#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea; Android Debug&#x1f7e7;&#x1f7e8;&#x1f7e9;&#x1f7e6;&#x1f7ea; Topic 发布安卓学习过程中遇到问题解决过程&#xff0c;希望我的解决方案可以对小伙伴们有帮助。 &#x1f680;write…
阅读更多...
最新文章

Copyright @ 2022~2023