题目描述

跑一遍 $floyd$ ,寻找最值条件
注意有可能所有异性对某个人的距离感都是最大值，所以 $dist$ 和 $df$ ，$dm$ 的最大值要统一。

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n;
int dist[N][N],sex[N];
int d[N]; //每个人和异性的最大距离
void floyd()
{
    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]);
            }
        }
    }
}
int main()
{
    cin>>n;
    memset(dist,0x3f,sizeof dist);
    for(int i=1;i<=n;i++)
    {
        dist[i][i] = 0;
        string sexx;int m;cin>>sexx>>m;
        if(sexx == "F") sex[i] = 0;
        else sex[i] = 1;
        for(int j=1;j<=m;j++)
        {
            int a,b;
            scanf("%d:%d",&a,&b);
            dist[i][a] = b; 
        }
    }
    floyd();
    //异性缘最好的人: 对于所有的异性，异性对ta的最大距离值最小
    //找到对于每个人，异性到ta的最大距离
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(sex[i] != sex[j]) 
            {
                d[i] = max(d[i], dist[j][i]);
            }
        }
    }
    int df = 0x3f3f3f3f, dm =  0x3f3f3f3f; //df和dm分别是女性和男性的大众情人的距离值
    for(int i=1;i<=n;i++)
    {
        if(sex[i] == 0) df = min(df,d[i]);
        else if(sex[i] == 1) dm = min(dm,d[i]);
    }
    vector<int> f,m;
    for(int i=1;i<=n;i++)
    {
        if(sex[i] == 0)
        {
            if(d[i] == df) f.push_back(i);
        }
        else if(sex[i] == 1)
        {
            if(d[i] == dm) m.push_back(i);
        }
    }
    for(auto i:f) cout<<i<<' ';
    cout<<'\n';
    for(auto i:m) cout<<i<<' '; 
    cout<<'\n';
    return 0;
}

```