L2-044 大众情人 测试点4

Question

为什么最后一个测试点过不去TT

#include <bits/stdc++.h>
using namespace std;

int n;
int d[510][510];
int sex[510];
int xlike[510];

int main(){
    cin>>n;
    memset(sex,0,sizeof(sex));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            d[i][j]=0x3f3f3f3f;
        }
    }
    for(int i=1;i<=n;i++){
        char x;
        cin>>x;
        if(x=='M')
            sex[i]=1;
        int k;
        cin>>k;
        for(int j=0;j<k;j++){
            int num,dis;
            char xx;
            cin>>num>>xx>>dis;
            d[i][num]=dis;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(d[i][j]>d[i][k]+d[k][j])
                    d[i][j]=d[i][k]+d[k][j];
            }
        }
    }
    for(int i=0;i<=1;i++){
        int minall=0x3f3f3f3f;
        for(int j=1;j<=n;j++){
            if(sex[j]==i){
                int maxd=0;
                for(int k=1;k<=n;k++){
                    if(sex[k]!=i&&d[k][j]>maxd)
                        maxd=d[k][j];
                }
                xlike[j]=maxd;
                if(maxd<minall)
                    minall=maxd;
            }
        }
        int flag=0;
        for(int j=1;j<=n;j++){
            if(sex[j]==i&&xlike[j]==minall){
                if(flag!=0)
                    cout<<" ";
                cout<<j;
                flag++;
            }
        }
        cout<<endl;
    }
    return 0;
}

Answer 1

该回答引用自GPT-3.5,由博主GISer Liu编写：

根据你提供的代码，我来分析一下可能导致最后一个测试点无法通过的原因。
在代码中，首先通过输入数据构建了一个图，然后使用了 Floyd-Warshall 算法计算了所有点对之间的最短路径。接着，通过遍历每个性别（0 或
1），找到每个性别中喜欢的异性的最长距离，最后输出距离最小的人的编号。
可能的问题及解决方案如下：

1. 内存溢出问题： 在题目中给出的测试数据中，可能存在比较大的数据量，导致数组 d 大小超过了内存限制，引发内存溢出。解决方法是优化算法或者使用动态内存分配。
2. 计算过程中的错误： 在使用 Floyd-Warshall 算法计算最短路径时，有可能出现计算错误或者死循环的情况。这可能是由于图的数据特性导致的，需要检查算法实现的正确性。可以通过手动计算一些简单的测试数据来验证算法的正确性。
3. 边界条件处理不当： 在遍历性别时，可能存在边界条件处理不当导致程序错误。例如，可能存在没有男性或女性的情况，但代码没有进行处理。需要确保程序对各种情况都进行了正确的处理。
4. 输出格式问题： 最后输出结果时，可能存在格式不正确导致判断错误的情况。确保输出格式符合题目要求，每个数字后面有且只有一个空格，并且每个性别的结果单独一行。
5. 代码逻辑错误： 可能存在逻辑错误导致程序不能正确输出结果。这需要仔细检查代码逻辑，特别是关键的条件判断和循环部分。
   针对以上可能的问题，你可以逐一检查并进行调试和修改。如果有具体的报错信息或者程序输出的错误结果，可以提供更多信息以便进行更具体的分析和解决。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订