社区讨论
P4017 40分 RE 了
学术版参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @lo9n6o60
- 此快照首次捕获于
- 2023/10/28 14:09 2 年前
- 此快照最后确认于
- 2023/10/28 14:09 2 年前
我这题用的拓扑排序,代码如下
CPP#include<bits/stdc++.h>
using namespace std;
const int mod = 80112002;
int n,m,a,b,l;
vector <int> e[5005];
queue <int> q;
int ans ;
int in[5005],out[5005],num[5005];
int main(){
cin>>n>>m;
for(int i=1 ; i<=m ; i++){
cin>>a>>b;
in[b]++ , out[a]++;
e[a].push_back(b);
}
for(int i=1 ; i<=m ; i++){
if(in[i] == 0){
num[i] = 1;
q.push(i);
// break;
}
}
while(!q.empty()){
int tot = q.front();
q.pop();
l=e[tot].size();
for(int i=0 ; i<l ; i++){
int nex = e[tot][i];
in[nex]--;
num[nex] = (num[nex] + num[tot]) % mod ;
if(in[nex] == 0){
q.push(e[tot][i]);
}
}
}
for(int i = 1; i <= n; ++i) {
if(!out[i]){
// cout<<num[i]<<" "<<ans<<endl;
ans = (ans + num[i]) % mod;
}
}
cout<<ans;
return 0;
}
另外 为什么最后要
CPP ans = (ans + num[i]) % mod;
我认为只要这样就行了:
CPPans = num[i] % mod;
是出度为零的比较多?(我感觉极度不对)
回复
共 4 条回复,欢迎继续交流。
正在加载回复...