SWUSTOJ #1063 带权有向图计算

SWUSTOJ #1063 带权有向图计算

  • 题目
    • 输入
    • 输出
    • 样例输入
    • 样例输出
  • 源代码

题目

假设带权有向图G采用邻接矩阵存储，计算图的最大权值、最小权值以及对应的有向边。

输入

第一行第一个整数n表示顶点的个数（顶点编号为0到n-1），第二行表示顶点i和j，接下来是为一个n*n大小的整数矩阵，表示图的邻接关系。数字为大于0表示邻接值，-1表示不邻接，对角线为0。

输出

第一行为最大权值，第二行为有向边。第三行为最小权值，第四行为有向边。
由于OJ无法显示尖括号，所以这里用圆扩号来表示有序对。

样例输入

5
0 5 -1 23 -1
-1 0 31 56 -1
-1 -1 0 -1 -1
-1 -1 -1 0 -1
56 -1 -1 19 0

样例输出

56
(1 3)(4 0)
5
(0 1)
注意：由于显示的问题，输出数据应采用尖括号。

源代码

#include <iostream>using namespace std;int main()
{int count1[100][2];int count2[100][2];int max = 0;int min = -1;int k;cin >> k;int arr[100][100];for (int i = 0; i < k; i++){for (int j = 0; j < k; j++){cin >> arr[i][j];if (arr[i][j] >= 0&&i!=j){if (min == -1){min = arr[i][j];}else if (arr[i][j] <= min){min = arr[i][j];}if (arr[i][j] >= max){max = arr[i][j];}}}}int m = 0;int n = 0;for (int i = 0; i < k; i++){for (int j = 0; j < k; j++){if (arr[i][j] == max){count1[m][0] = i;count1[m][1] = j;m++;}if (arr[i][j] == min){count2[n][0] = i;count2[n][1] = j;n++;}}}cout << max <<endl;for (int i = 0; i < m; i++){cout << '<' << count1[i][0]<<" "<< count1[i][1] << '>';}cout << endl;cout << min << endl;for (int i = 0; i < n; i++){cout << '<' << count2[i][0]<<" " << count2[i][1] << '>';}return 0;
}