L2-044 大众情人

思路

• 题目定义的两个人之间的距离是最小距离并且是可以传递的。所以用Floyd求出任何两个人之间的最小距离
• 异性缘说的是，异性对本人的距离。所以在枚举的时候，如果评女性（x）的异性缘, 对于每个男性(y)， 我们找的是g[y][x]的最大值, 而不是g[x][y]。
• 有一个坑点是，如果两个人之间没有距离，我们初始化为正无穷，在考虑异性缘的时候这样的人不能直接不考虑，如代码63和91行
• 上述情况距离正无穷说明，异性缘1/d，是负无穷，这是符合题意的
• 对于男女分别讨论的题我们一般，直接把男生和女生分别存起来。
• 男女的处理一般相同，所以我们尽量把处理操作写成函数，增加阅读性，减上代码的重复

#include <bits/stdc++.h>
//#define int long long
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
vector<int> male, fmale;
int g[N][N]; // 有向图
int n;
struct node
{
    int id, d;
    bool operator < (const node& t) const
    {
        if(d != t.d) return d < t.d;
        return id < t.id;
    }
};
void Floyd()
{
    for(int k = 1; k <= n; k ++)
    {
        for(int i = 1; i <= n; i ++)
        {
            for(int j = 1; j <= n; j ++)
            {
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
}
void get_max(int sex, vector<node>& vec)
{
    vector<int> a, b;
    // 女性
    if(sex == 1)
    {
        a = fmale;
        b = male;
    }
    else
    {
        a = male;
        b = fmale;
    }
    for(int i = 0; i < a.size(); i ++)
    {
        int max_d = 0, x, y;
        for(int j = 0; j < b.size(); j ++)
        {
            x = a[i], y = b[j];
            if(g[y][x] > max_d) max_d = g[y][x];
        }
        vec.push_back({x, max_d});
    }
}
signed main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        char c;
        int k;
        cin >> c;
        if(c == 'F') fmale.push_back(i);
        else male.push_back(i);
        cin >> k;
        g[i][i] = 0;
        for(int j = 0; j < k; j ++)
        {
            int id, d;
            scanf("%d:%d", &id, &d);
            g[i][id] = min(g[i][id], d);
            //g[i][id] = d;
        }
    }

    // Floyd，确定任何两人人之间的最短路
    Floyd();

    // 输出女性大众情人
    vector<node> resf; // 记录每个女性，距离最长的异性
    get_max(1, resf);
    sort(resf.begin(), resf.end());
    int min_d = resf[0].d;
    for(int i = 0; i < resf.size(); i ++)
    {
        if(resf[i].d == min_d)
        {
            if(i == 0) cout << resf[i].id;
            else cout << ' ' << resf[i].d;
        }
        else break;
    }
    cout << endl;

    // 输出男性大众情人
    vector<node> resm;
    get_max(0, resm);
    sort(resm.begin(), resm.end());
    min_d = resm[0].d;
    for(int i = 0; i < resm.size(); i ++)
    {
        if(resm[i].d == min_d)
        {
            if(i == 0) cout << resm[i].id;
            else cout << ' ' << resm[i].id;
        }
        else break;
    }
    return 0;
}