3. 图的应用之——图的连通
题目描述
给定一个图的邻接矩阵，请判断该图是否是连通图。连通图：任意两个顶点之间都有路径。
–程序要求–
若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
第1行输入一个整数k，表示有k个测试数据
第2行输入一个整数n，表示有n个结点
从第3行起到第n+2行输入一个邻接矩阵，其中Matrix[i,j]=1表示第i，j个结点之间有边，否则不存在边。
接下来是第2到第k个测试数据的结点数和邻接矩阵
输出
输出Yes or No表示图是否是强连通图
输入样例
2
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
7
0 1 0 0 0 0 0
0 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
输出样例
Yes
No
参考代码
#include<iostream> using namespace std; const int MaxLen = 20; class Map { private: bool Visit[MaxLen]; int Matrix[MaxLen][MaxLen]; int Vexnum; void DFS(int v) { int w, i, k; Visit[v] = true; count1++; //cout<<v<<" "; //寻找邻接点 int *AdjVex = new int[Vexnum]; for (i = 0; i < Vexnum; i++) AdjVex[i] = -1; k = 0; for (i = 0; i < MaxLen; i++) if (Matrix[v][i] == 1) AdjVex[k++] = i; i = 0; for (w = AdjVex[i++]; w >= 0; w = AdjVex[i++]) { if (Visit[w] == false) DFS(w); } delete[]AdjVex; } public: int count1; void SetMatrix(int vnum, int mx[MaxLen][MaxLen]) { int i, j; Vexnum = vnum; for (i = 0; i < MaxLen; i++) for (j = 0; j < MaxLen; j++) Matrix[i][j] = 0; for (i = 0; i < Vexnum; i++) for (j = 0; j < Vexnum; j++) Matrix[i][j] = mx[i][j]; } void DFSTraverse() { int v, i; for (i = 0; i < Vexnum; i++) Visit[i] = false; for (v = 0; v < Vexnum; v++) if (!Visit[v]) DFS(v); cout << endl; } int lt() { int i, j; for (i = 0; i < Vexnum; i++) { for (j = 0; j < Vexnum; j++) Visit[j] = false; count1 = 0; DFS(i); if (count1 != Vexnum) return 0; } return 1; } }; int main() { int t; cin >> t; while (t--) { int n, i, j; cin >> n; int a[MaxLen][MaxLen]; for (i = 0; i < n; i++) for (j = 0; j < n; j++) cin >> a[i][j]; Map map; map.SetMatrix(n, a); if (map.lt()) cout << "Yes" << endl; else cout << "No" << endl; } }
4. 广度优先搜索-STL对象版
题目描述
给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始
注意：图n个顶点编号从0到n-1
输入
第一行输入t，表示有t个测试实例
第二行输入n，表示第1个图有n个结点
第三行起，每行输入邻接矩阵的一行，以此类推输入n行
第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开
以此类推输入下一个示例
输出
每行输出一个图的广度优先搜索结果，结点编号之间用空格隔开
输入样例
2
4
0 0 1 1
0 0 1 1
1 1 0 1
1 1 1 0
5
0 0 0 1 1
0 0 1 0 0
0 1 0 1 1
1 0 1 0 0
1 0 1 0 0
输出样例
0 2 3 1
0 3 4 2 1
参考代码
#include<iostream> #include<queue> using namespace std; const int MaxLen = 20; class Map { private: bool visited[MaxLen]; int Matrix[MaxLen][MaxLen]; int vexnum; void BFS(int v); public: void SetMatrix(int vnum, int mx[20][20]); void BFSTraverse(); }; void Map::SetMatrix(int vnum, int mx[20][20]) { int i, j; vexnum = vnum; for (i = 0;i < vexnum;i++) for (j = 0;j < MaxLen;j++) Matrix[i][j] = 0; for (i = 0;i < vexnum;i++) for (j = 0;j < vexnum;j++) Matrix[i][j] = mx[i][j]; } void Map::BFSTraverse() { /*int v; int i; for (i = 0;i < vexnum;i++) { visited[i] = false; } for (v = 0;v < vexnum;v++) { if (visited[v] == false)DFS(v); } cout << endl;*/ BFS(0); } void Map::BFS(int v) { int w, u; int i, k; int* AdjVex = new int[vexnum]; for (i = 0;i < vexnum;i++) AdjVex[i] = -1; queue<int>Q; for (i = 0;i < vexnum;i++) visited[i] = false; for (v = 0;v < vexnum;++v) { if (!visited[v]) { visited[v] = true; cout << v << " "; Q.push(v); while (!Q.empty()) { u = Q.front(); Q.pop(); for(i=0,k=0;i<vexnum;i++) if (Matrix[u][i] == 1) { AdjVex[k] = i; k++; } for (i = 0, w = 0;;i++) { w = AdjVex[i]; if (w == -1)break; if (!visited[w]) { visited[w] = true; cout << w << " "; Q.push(w); } } } } } cout << endl; } int main() { int t; int n; int i, j, k; int mx[20][20]; cin >> t; for (i = 0;i < t;i++) { cin >> n; for (j = 0;j < n;j++) for (k = 0;k < n;k++) cin >> mx[j][k]; Map m; m.SetMatrix(n, mx); m.BFSTraverse(); } return 0; }
5. 货币套汇（图路径）
题目描述
套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定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<cstring> #include<cmath> #include<map> #include<utility> using namespace std; #define INF 0x3f3f3f3f #define MAX 45 double path[MAX][MAX]; map<string, int>ratemap; bool Floyd(int n) { for (int k = 0;k < n;k++) { for (int i = 0;i < n;i++) { for (int j = 0;j < n;j++) { if (path[i][j] < path[i][k] * path[k][j]) path[i][j] = path[i][k] * path[k][j]; } } } for (int i = 0;i < n;i++) { if (path[i][i] > 1) return true; } return false; } int main() { int n, m, count = 1; int t; cin >> t; string nameA, nameB, name; double rate; while (t--) { memset(path, 0, sizeof(path)); cin >> n >> m; for (int i = 0;i < n;i++) { cin >> name; pair<string, int>a(name, i); ratemap.insert(a); path[i][i] = 1; } //cin >> m; for (int i = 0;i < m;i++) { cin >> nameA >> rate >> nameB; path[ratemap[nameA]][ratemap[nameB]] = rate; } if (Floyd(n)) cout <<"YES" << endl; else cout <<"NO" << endl; count++; ratemap.clear(); } return 0; }
