摘要
Title: L2-044 大众情人
Tag: floyd
Memory Limit: 64 MB
Time Limit: 1000 ms

L2-044 大众情人

题意

人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比，并且距离感是单向的。例如小蓝对小红患了单相思，从小蓝的眼中看去，他和小红之间的距离为 1，只差一层窗户纸；但在小红的眼里，她和小蓝之间的距离为 108000，差了十万八千里…… 另外，我们进一步假定，距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2，则即使小绿并不直接认识小红，我们也默认小绿早晚会认识小红，并且因为跟小蓝很亲近的关系，小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题，如果小绿本来也认识小红，或者他通过其他人也能认识小红，但通过不同渠道推导出来的距离感不一样，该怎么算呢？我们在这里做个简单定义，就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。
一个人的异性缘不是由最喜欢他/她的那个异性决定的，而是由对他/她最无感的那个异性决定的。我们记一个人 i 在一个异性 j 眼中的距离感为 D ij；将 i 的“异性缘”定义为 1/max j∈S(i){D ij}，其中 S(i) 是相对于 i 的所有异性的集合。那么“大众情人”就是异性缘最好（值最大）的那个人。
本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。
思路

做一遍floyd找出男对女，女对男的每个人的距离最小值，取出最大值
再一起取个最小值，找到和这个最小值值相等的编号即可

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 550, INF = 0x3f3f3f3f;

int n;
int dist[N][N], d[N];
char a[N];

signed main()
{
    memset(dist, INF, sizeof dist);
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        getchar();
        char sex;
        scanf("%c", &sex);
        a[i] = sex;
        int k, v, w;
        scanf("%d", &k);
        while (k--)
        {
            scanf("%d:%d", &v, &w);
            dist[i][v] = w;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i == j)
                dist[i][i] = 0;
        }
    }
    for (int k = 1; k <= n; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= n; ++j)
            {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (a[i] != a[j])
                d[i] = max(d[i], dist[j][i]);

    vector<int> ansm, ansf;
    int mnm = INF, mnf = INF;

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 'M')
            mnm = min(mnm, d[i]);
        else
            mnf = min(mnf, d[i]);
    }

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 'M')
            continue;
        if (d[i] == mnf)
            ansf.push_back(i);
    }

    for (int i = 1; i <= n; i++)
    {
        if (a[i] == 'F')
            continue;
        if (d[i] == mnm)
            ansm.push_back(i);
    }

    printf("%d", ansf[0]);
    for (int i = 1; i < SZ(ansf); ++i)
    {
        printf(" %d", ansf[i]);
    }
    printf("\n%d", ansm[0]);
    for (int i = 1; i < SZ(ansm); ++i)
    {
        printf(" %d", ansm[i]);
    }
    return 0;
}

L2-044 大众情人

题意

思路

代码