人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人 在一个异性 眼中的距离感为 ；将 的“异性缘”定义为 ，其中 是相对于 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。
本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。
输入格式：
输入在第一行中给出一个正整数 ，为总人数。于是我们默认所有人从 到 编号。
随后 行，第 行描述了编号为 的人与其他人的关系，格式为：
性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K
其中 性别 是这个人的性别，F 表示女性，M 表示男性；K（<N 的非负整数）为这个人直接认识的朋友数；随后给出的是这 K 个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过 的正整数。
题目保证给出的关系中一定两种性别的人都有，不会出现重复给出的关系，并且每个人的朋友中都不包含自己。
输出格式：
第一行给出自身为女性的“大众情人”的编号，第二行给出自身为男性的“大众情人”的编号。如果存在并列，则按编号递增的顺序输出所有。数字间以一个空格分隔，行首尾不得有多余空格。
输入样例：
6
F 1 4:1
F 2 1:3 4:10
F 2 4:2 2:2
M 2 5:1 3:2
M 2 2:2 6:2
M 2 3:1 2:5输出样例：
2 3
4思路
表示 与 是朋友, 且在 眼中的距离感为 。我们要求的就是 点被所有异性 认为的距离感的最大值。然后再从小到大输出最大值最小的 编号。
故先用 floyd 求出所有人关于其他人的距离感, 接着枚举所有人, 对于当前人 , 枚举除 以外的所有人 , 如果他俩不是同一个性别, 那么就更新 的最大距离感 。同时记录两个性别的距离最小值。
最后遍历一次女性, 输出 的人的编号, 再遍历一次男性, 同样也是输出 的人的编号。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
const int N = 550, INF = 0x3f3f3f3f;
int g[N][N]; // 第i个人被j所看的距离感
int d[N]; // 每个人被别人感觉到的最大距离感
int famle[N]; // 每个点的性别
int n;
void floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if(g[i][j] > g[i][k] + g[k][j])
g[i][j] = g[i][k] + g[k][j];
}
int main()
{
memset(g, 0x3f, sizeof g);
cin >> n;
char op[2];
for (int i = 1; i <= n; i++)
{
int m;
cin >> op >> m;
if (op[0] == 'F')
famle[i] = 1;
else
famle[i] = 2;
for (int j = 1; j <= m; j++)
{
int t, d;
scanf("%d:%d", &t, &d);
g[i][t] = d;
}
}
floyd();
int fmin = INF, mmin = INF;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (famle[i] != famle[j])
d[i] = max(d[i], g[j][i]);
}
if(famle[i] == 1 && d[i]) fmin = min(fmin, d[i]);
else if(famle[i] == 2 && d[i]) mmin = min(mmin, d[i]);
}
for(int i = 1, j = 0; i <= n; i++) // 输出女
if(famle[i] == 1 && d[i] == fmin)
{
if(j) printf(" ");
j++;
printf("%d",i);
}
printf("\n");
for(int i = 1, j = 0; i <= n; i++) // 输出男
if(famle[i] == 2 && d[i] == mmin)
{
if(j) printf(" ");
j++;
printf("%d",i);
}
printf("\n");
return 0;
}