题目解析
给定n个人
性别 以及 每个人对k个人的距离感
求出女生和男生异性缘最好的人
解题思路
先读题
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的
也就是 i 到 j 的感觉距离中取最大值 组成 S(i)
- 然后再在 S(i) 中 取最小值
- 这样得到的值就会使最小的 也就是异性缘最好的
所以直接找男生女生中的最小感觉距离即可
为什么是最短路中呢？
因为题目中的
- 如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
所以得知是最短路
如何求每个人到另一个人的感觉距离呢？
floyd
先求出每个人之间的感觉距离
然后再找出异性间的感觉距离 求出最远感觉距离得到数组S
然后找女生男生的最小值即可
然后再输出
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int inf = 0x3f3f3f3f;
public static void main(String[] args) throws IOException
{
int n = Integer.valueOf(sc.readLine());
// 存储每个人对另一个人的感觉距离
long map[][] = new long[n + 10][n + 10];
for (int i = 1; i <= n; i++)
{
Arrays.fill(map[i], inf);
map[i][i] = 0;
}
// 存储是否为女生
boolean sex[] = new boolean[n + 10];
for (int a = 1; a <= n; a++)
{
String str[] = sc.readLine().split(" ");
sex[a] = str[0].equals("F");
int k = Integer.valueOf(str[1]);
for (int i = 1; i <= k; i++)
{
String s[] = str[i + 1].split(":");
int b = Integer.valueOf(s[0]), c = Integer.valueOf(s[1]);
// 当前 a 到 b 的感觉距离为 c
map[a][b] = c;
}
}
// floyd 求每个人到另一个人的感觉距离
// 中间的踏板
// 也就是 i -> k -> j
for (int k = 1; k <= n; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
// 距离更小就替换
if (map[i][j] > map[i][k] + map[k][j])
map[i][j] = map[i][k] + map[k][j];
}
}
}
// S[i] 表示对第i个人的感觉距离最远的距离
long S[] = new long[n + 10];
long minF = inf, minM = inf;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
// 要为异性
if (sex[i] != sex[j])
// 寻找最大的感觉距离
S[i] = Math.max(S[i], map[j][i]);
}
if (sex[i])
minF = Math.min(minF, S[i]);
else
minM = Math.min(minM, S[i]);
}
// 输出异性缘最大的女生的
int pos = 0;
for (int i = 1; i <= n; i++)
{
if (sex[i] && minF == S[i])
{
if (pos++ > 0)
out.print(" ");
out.print(i);
}
}
out.println();
// 输出异性缘最大的男生
pos = 0;
for (int i = 1; i <= n; i++)
{
if (!sex[i] && minM == S[i])
{
if (pos++ > 0)
out.print(" ");
out.print(i);
}
}
out.flush();
out.close();
}
static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(System.out);
}