一个国家有N个公民，标记为0,1,2，…，N-1，每个公民有一个存款额。已知每个公民有一些朋友，同时国家有一条规定朋友间的存款额之差不能大于d。也就是说，a和b是朋友的话，a有x元的存款，b有y元，那么|x-y|<=d。给定d值与N个人的朋友关系，求这个国家最富有的人和最贫穷的人的存款相差最大的可能值是多少？即求贫富差距的最大值的下界。若这个值为无穷大，输出-1.
Input
|
1 2 3 4 5 |
多组测试数据，第一行一个整数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]. |
Output
|
1 |
每组数据一行输出，即这个国家的贫富差距最大值的下界，如果这个值为无穷大输出-1. |
Input示例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
3 3 10 NYN YNY NYN 2 1 NN NN 6 1000 NNYNNN NNYNNN YYNYNN NNYNYY NNNYNN NNNYNN |
Output示例
|
1 2 3 |
20 -1 3000 |
题意可转化为求一有向图中相聚最远的点之间的距离，显然，当图不连通时贫富差距的值可以为无穷大。
枚举每一点作为起点，以该点为起点dfs或bfs找出距离其最远的点，记录距离。
对于枚举的每个起点得到的距离取其中的最大值，得到的结果乘以d即是题目所求的贫富差距最大值。
需要注意的是，图的直径不能以求树的直径的方法（两次dfs或bfs，第一次求出起点，第二次以起点得出直径）做，存在如
1-2
1-3
1-4
2-3
3-4
这样的反例，第一次搜索找到的起点可为2，3，4中的任意一点，当以3为第二次搜索的起点时得到的最终的直径为1，而该例子显然直径应为2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include <cstdio> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <istream> #define forr(a,b,c) for(int a=b;a<=c;a++) #define MAX(a,b) (a>b)?a:b; #define MIN(a,b) (a<b)?a:b; #define memsett(a) memset(a,sizeof(a),0); using namespace std; bool isfriend[100][100]; int linknum[100]; string s; int n, d,t,maxnum,maxmoney; void findfriends(int num) { forr(i, 1, n) { if (isfriend[num][i] == true && linknum[i] > linknum[num] + 1) { linknum[i] = linknum[num] + 1; findfriends(i); } } } int main() { scanf("%d", &t); forr(q, 1, t) { scanf("%d %d", &n, &d); forr(i,0,n) { linknum[i] = 1000; } linknum[1] = 0; getline(cin, s); forr(i, 1, n) { getline(cin, s); forr(j, 0, n - 1) { if (s[j] == 'Y')isfriend[i][j + 1] = true; else isfriend[i][j+1] = false; } } findfriends(1); maxnum = 1; maxmoney = 0; forr(i, 1, n) { if (linknum[i] > linknum[maxnum])maxnum = i; } if (linknum[maxnum] == 1000) { printf("-1\n"); } else { forr(i, 1, n) { maxnum = i; forr(j, 0, n) { linknum[j] = 1000; } linknum[maxnum] = 0; findfriends(maxnum); forr(j, 1, n) { if (linknum[j] > linknum[maxnum])maxnum = j; } maxmoney = MAX(maxmoney,linknum[maxnum]); } printf("%d\n", d*maxmoney); } } } |