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
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;
}