哮着写代码 2022-02-07 10:51 采纳率: 0%
浏览 49
已结题

一个拓扑排序的问题,OJ一直报运行错误

题目描述

PIPI开了一个工厂,工厂里面有许许多多的员工。每次要发工资的时候PIPI就开始思考了,如何才能给员工发最少的工资呢?
发工资的原则是这样的: 每个员工的工资都是一个整数,其中基本工资是888元,但是如果 A 是 B的上司,那么A的工资就要比B高。
现在给出员工的数量和员工之间的关系,PIPI想问下胖虎他最少要发多少钱??
输入
输入包含多组测试用例。
对于每一组测试用例,第一行包含两个整数 n (n<=10000)和 m (m<=20000)。表示PIPI工厂里面员工数量以及员工之间的关系数目。
接下来m行每一行包含两个整数 a和 b 。代表 a 是 b的的上司(1<=a,b<=n)。
输出
对于每组测试用例,输出PIPI最少需要发多少工资。如果PIPI没办法发工资,输出-1。
样例输入
2 1
1 2
2 2
1 2
2 1
样例输出
1777
-1

问题相关代码,请勿粘贴截图

#include <bits/stdc++.h>
using namespace std;
#define max 10005
int mp[max][max],visit[max],in[max],n,m;//mp为记录图的邻接矩阵,in记录图中各元素入度 
long long ans=0,base=888;//base为基础工资 
bool topsort(){
    queue<int> s;queue<int> q;//s用以记录入度为0的元素,q用以记录s中元素在图中层次,初始为0 
    for(int i=1;i<=n;i++) if(!in[i]) s.push(i),visit[i]=1,q.push(0);
    while((!s.empty())&&(!q.empty())){
        int t=s.front();int l=q.front();
        s.pop();q.pop();
        ans=ans+base+l;
        for(int i=1;i<=n;i++){
            if(mp[t][i]&&(!visit[i])) in[i]--;
            if((in[i]==0)&&(!visit[i])) s.push(i),visit[i]=1,q.push(l+1);
        } 
    }
    for(int i=1;i<=n;i++){
        if(!visit[i]) return false;
    }
    return true;
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        ans=0;
        memset(visit,0,sizeof(visit));
        memset(in,0,sizeof(in));
        memset(mp,0,sizeof(mp));
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            mp[b][a]=1;
            in[a]++;
        }
        bool r=topsort();
        if(r){
            printf("%lld\n",ans);
        }
        else printf("-1\n");
    }
    
    
}



运行结果及报错内容

样例在本地都是能通过的,但是OJ一直在报运行错误
Runtime Error:Segmentation fault
Runtime Error:Segmentation fault
Runtime Error:Segmentation fault
Runtime Error:Segmentation fault
辅助解释:
Segmentation fault:段错误,检查是否有数组越界,指针异常,访问到不应该访问的内存区域

我的解答思路和尝试过的方法

我觉得唯一可能越界的情况就是队列在pop()时下溢出,但是我每次pop前都判空了,就很迷

我想要达到的结果
  • 写回答

1条回答 默认 最新

  • 关注

    题目要求里m<=20000,代码中max 10005这个定义的数组大小可能不够,把 #define max 10005改大一些
    #define max 20005

    评论

报告相同问题?

问题事件

  • 已结题 (查看结题原因) 5月24日
  • 创建了问题 2月7日

悬赏问题

  • ¥15 问题遇到的现象和发生背景 360导航页面千次ip是20元,但是我们是刷量的 超过100ip就不算量了,假量超过100就不算了 这是什么逻辑呢 有没有人能懂的 1000元红包感谢费
  • ¥30 计算机硬件实验报告寻代
  • ¥15 51单片机写代码,要求是图片上的要求,请大家积极参与,设计一个时钟,时间从12:00开始计时,液晶屏第一行显示time,第二行显示时间
  • ¥15 用C语言判断命题逻辑关系
  • ¥15 原子操作+O3编译,程序挂住
  • ¥15 使用STM32F103C6微控制器设计两个从0到F计数的一位数计数器(数字),同时,有一个控制按钮,可以选择哪个计数器工作:需要两个七段显示器和一个按钮。
  • ¥15 在yolo1到yolo11网络模型中,具体有哪些模型可以用作图像分类?
  • ¥15 AD9910输出波形向上偏移,波谷不为0V
  • ¥15 淘宝自动下单XPath自动点击插件无法点击特定<span>元素,如何解决?
  • ¥15 曙光1620-g30服务器安装硬盘后 看不到硬盘