51NOD - 贫富差距(最短路)

题目链接:https://www.51nod.com/Challenge/Problem.html#!#problemId=1366

• 时间限制 1 秒 空间限制 131,072 KB

题目描述

一个国家有N个公民，标记为0,1,2，...，N-1，每个公民有一个存款额。已知每个公民有一些朋友，同时国家有一条规定朋友间的存款额之差不能大于d。也就是说，a和b是朋友的话，a有x元的存款，b有y元，那么|x-y|<=d。给定d值与N个人的朋友关系，求这个国家最富有的人和最贫穷的人的存款相差最大的可能值是多少？即求贫富差距的最大值的下界。若这个值为无穷大，输出-1.

输入

多组测试数据，第一行一个整数T，表示测试数据数量，1<=T<=5
每组测试数据有相同的结构构成。
每组数据的第一行两个整数N，d，表示人数与朋友间存款差的最大值，其中2<=N<=50,0<=d<=1000.
接下来有一个N*N的数组A，若A[i][j]='Y'表示i与j两个人是朋友，否则A[i][j]='N'表示不是朋友。其中A[i][i]='N'，且保证
A[i][j]=A[j][i].

输出

每组数据一行输出，即这个国家的贫富差距最大值的下界，如果这个值为无穷大输出-1.

输入样例

3
3 10
NYN
YNY
NYN
2 1
NN
NN
6 1000
NNYNNN
NNYNNN
YYNYNN
NNYNYY
NNNYNN
NNNYNN

输出样例

20
-1
3000

解题思路

就是在最短路里面找最大值。

#include 
#include 
const int inf = 99999999;
int map[55][55], n;
void Floyd()
{for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)for (int k = 0; k < n; k++)if (map[j][k] > map[j][i] + map[i][k])map[j][k] = map[j][i] + map[i][k];
}
int main()
{int d, t, ans;char str[55][55];scanf("%d", &t);while (t--){ans = -inf;scanf("%d%d", &n, &d);for (int i = 0; i < n; i++)scanf("%s", str[i]);for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (str[i][j] == 'Y')map[i][j] = 1;else{if (i != j)map[i][j] = inf;else map[i][j] = 0;}}}Floyd();for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (ans < map[i][j])ans = map[i][j];if (ans < inf)printf("%d\n", ans * d);else printf("-1\n");}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！