社区讨论

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;
我认为只要这样就行了:
CPP
ans = num[i] % mod;
是出度为零的比较多?(我感觉极度不对)

回复

4 条回复,欢迎继续交流。

正在加载回复...