[gplt] 2022 popular lover (Floyd)

There is about an hour to write about this popular lover during the game , Burst by the network card （, The newly written code is ready for submission , Network timeout ...oms Direct card return .. Roll in again and knock again to hand in the card .. Today, I found a place where I could hand in the questions, so I adjusted it bug,ac 了 （ You still have to be careful when typing code in the evaluation system , In the future, I will write in the local compiler ,）

Title Description ：

Input ：

Output & Examples ：

The title is a little smelly and long , Roughly explain the meaning of the topic

Yes N personal , Men and women ,a->b（a Yes b It matters , The sense of distance is num1),b->c（b Yes c It matters , The sense of distance is num2) You can have a->c（a Yes c It matters , The sense of distance is num1+num2). Because a person's heterosexual relationship is determined by the person who is the most indifferent to him , therefore A The heterosexual relationship can be transformed into A All the opposite sex are right A The value of the maximum sense of distance （ Most senseless ）. The lover of the public is the one with the largest distance and the smallest distance between the opposite sex among the same-sex people （ There can be multiple ）  Output the popular lover among women and the popular lover among men .

take N The relationships between individuals are connected into a directed graph （ Note that it is not an undirected graph ,a->b And b->a The sense of distance can vary ）. Because everyone is required to have everything The opposite sex treats him / she The shortest distance （ Relationships can deliver ）, so , It can be transformed into multi-source shortest path problem .

N<=500, The data range is not very large , You can directly consider simple and rude Floyd（ The core algorithm is only five lines ！）.1. Find the shortest path between any two . 2. Ask everyone again / Her heterosexual relationship （ The decision with the greatest distance ） For convenience , I directly used two structure arrays to record female and male Opposite sex and oneself The maximum distance . 3. Sort them from small to large , The one with the largest and smallest distance from the opposite sex is the public lover , Output directly .

See code for details ：

#include <bits/stdc++.h>
using namespace std;
struct node
{
    char sex;                // Gender 
    int idx, num;            // Corresponding to subscript and maximum distance respectively （ Heterosexual reasons for him / The opposite sex she's least interested in ）
} a[510], b[510], c[510];    // a Save the initial input data of everyone ,b Save female data ,c Save male 
int e[510][510], cnt1, cnt2; // cnt1 Record the number of women ,cnt2 Record the number of men 
bool cmp(node x, node y)
{
    if (x.num == y.num)
        return x.idx < y.idx;
    return x.num < y.num;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) // floyd initialization （ Initially, there is no relationship between the two , Set to inf）
        for (int j = 1; j <= n; j++)
            if (i != j)
                e[i][j] = 1e9;
            else
                e[i][j] = 0;
    for (int i = 1; i <= n; i++)
    {
        getchar(); // Absorb the last line break 
        int m;
        scanf("%c%d", &a[i].sex, &m);
        a[i].idx = i; // Deposit subscript 
        for (int j = 1; j <= m; j++)
        {
            int x, y;
            scanf("%d:%d", &x, &y);
            e[i][x] = y; // i->x The distance to y
        }
    }
    for (int k = 1; k <= n; k++)                 // Enumerate transit points 
        for (int i = 1; i <= n; i++)             // Enumeration starting point 
            for (int j = 1; j <= n; j++)         // Enumerate endpoints 
                if (e[i][j] > e[i][k] + e[k][j]) // Can pass k to update i,j The distance is updated i,j One of the most short circuit 
                    e[i][j] = e[i][k] + e[k][j];
    for (int i = 1; i <= n; i++) // Ask everyone for the opposite sex 
    {
        int res = 0; // The current heterosexual relationship , To find the one with the largest distance, the initial value is the minimum , I'm going to set it to 0
        int j;
        for (j = 1; j <= n; j++)
        {
            if (a[i].sex != a[j].sex)    // j And i For the opposite sex -> Update heterosexual relationship 
                res = max(res, e[j][i]); // Be careful ！ yes j->i instead of i->j, Because it is the distance between the opposite sex and oneself 
        }
        if (a[i].sex == 'F') // i For women , Put her subscript , Heterosexual value is stored in b
        {
            b[++cnt1].num = res;
            b[cnt1].idx = a[i].idx;
        }
        else // i For men , Put his subscript , Heterosexual value is stored in c
        {
            c[++cnt2].num = res;
            c[cnt2].idx = a[i].idx;
        }
    }
    sort(b + 1, b + 1 + cnt1, cmp); // Sort to find the one with the smallest distance from the opposite sex 
    sort(c + 1, c + 1 + cnt2, cmp);
    int i = 1, ok = 0;
    while (b[i].num == b[1].num && i <= cnt1) // Output all the women in parallel 
    {
        if (ok)
            cout << " "; // Output format processing , There must be no extra space at the end of the line 
        cout << b[i].idx;
        i++;
        ok = 1;
    }
    i = 1;
    ok = 0;
    cout << endl;
    while (c[i].num == c[1].num && i <= cnt2) // Output all juxtaposed men 
    {
        if (ok)
            cout << " ";
        cout << c[i].idx;
        i++;
        ok = 1;
    }
}

The code can be a bit lengthy , But the idea is still relatively simple

ending

If there are any mistakes, please correct them ！ Thank you for ！