题目描述
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前都判空了,就很迷