题目描述
人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为108000，差了十万八千里……我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为1+2=当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人i在一个异性j眼中的距离感为Dij；将i的“异性缘”定义为1/maxj∈S{Dij}，其中S是相对于i的所有异性的集合。那么“大众情人”就是异性缘最好的那个人。
本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。
输入格式：
输入在第一行中给出一个正整数N，为总人数。于是我们默认所有人从1到N编号。
随后N行，第i行描述了编号为i的人与其他人的关系，格式为：
性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K
其中性别是这个人的性别，F表示女性，M表示男性；K为这个人直接认识的朋友数；随后给出的是这K个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过10^6的正整数。
题目保证给出的关系中一定两种性别的人都有，不会出现重复给出的关系，并且每个人的朋友中都不包含自己。
输出格式：
第一行给出自身为女性的“大众情人”的编号，第二行给出自身为男性的“大众情人”的编号。如果存在并列，则按编号递增的顺序输出所有。数字间以一个空格分隔，行首尾不得有多余空格。
输入样例：
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
思路：
#include <bits/stdc++.h>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n;
char sex[N];
int d[N][N];
int main() {
cin >> n;
memset(d, 0x3f, sizeof d);
for (int i = 1; i <= n; i ++) d[i][i] = 0;
for (int i = 1; i <= n; i ++) {
char s[2];
int cnt;
cin >> s >> cnt;
sex[i] = s[0];
while (cnt -- ) { // cnt对朋友
char ch;
int id, dist;
cin >> id >> ch >> dist;
d[i][id] = dist;
}
}
for (int k = 1; k <= n; k ++)
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (auto c : string("FM")) {
int mn = INF;
for (int i = 1; i <= n; i ++)
if (sex[i] == c) {
int mx = 0;
for (int j = 1; j <= n; j ++)
if (sex[i] != sex[j])
mx = max(mx, d[j][i]);
mn = min(mn, mx);
}
bool is_first = true;
for (int i = 1; i <= n; i ++)
if (sex[i] == c) {
int mx = 0;
for (int j = 1; j <= n; j ++)
if (sex[i] != sex[j])
mx = max(mx, d[j][i]);
if (mx == mn) {
if (is_first) is_first = false;
else cout << " ";
printf("%d", i);
}
}
puts("");
}
return 0;
}
文章为作者独立观点，不代表 股票程序化软件自动交易接口观点
相关文章
股民评论