做网站报价单,wordpress ip修改,怀化找工作网站,个人简历模板word可编辑A. DS图—图的最短路径#xff08;无框架#xff09;题目描述给出一个图的邻接矩阵#xff0c;输入顶点v#xff0c;用迪杰斯特拉算法求顶点v到其它顶点的最短路径。输入第一行输入t#xff0c;表示有t个测试实例第二行输入顶点数n和n个顶点信息第三行起#xff0c;每行输…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
V00-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且编号最小的顶点v2.输出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() {cinvexNum;matrix new int*[vexNum];visit new bool[vexNum];for(int i0;ivexNum;i){visit[i] false;matrix[i] new int[vexNum];for(int j0;jvexNum;j)cinmatrix[i][j];}
}Graph::~Graph() {delete visit;for(int i0;ivexNum;i)delete []matrix[i];delete []matrix;
}void Graph::TopSort() {for(int k0;kvexNum;k){int vinDegreeZero();coutv ;visit[v] true;for(int i0;ivexNum;i)matrix[v][i]0;}coutendl;
}int Graph::inDegreeZero() {for(int col0;colvexNum;col){bool flag true;for(int row0;rowvexNum;row){if(matrix[row][col]!0)flag false;}if(flag !visit[col])return col;}return -1;
}int main()
{int t;cint;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代码#includeiostream
#includemath.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.161.064美元从而获得6.4%的利润。 给定n种货币c1 ,c2 ,... ,cn的有关兑换率试设计一个有效算法确定货币间是否存在套汇的可能性。提示判断图上是否出现正环,即环上所有的边相乘大于1输入第一行测试数据组数每组测试数据格式为第一行正整数n (1 n 30)正整数m分别表示n种货币和m种不同的货币兑换率。2~n1行n种货币的名称。n2~nm1行每行有3 个数据项cirij 和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
#includestring
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;
}
