书海扬帆的博客

根据题意,题目给定的图是一个DAG(有向无环图)。

我们分别记录入度和出度,易知食物链的起点出度一定为1,终点入度一定为1,这个自己画一下自然就能明白。

接下来就是基本的拓扑排序。用了STL中的队列实现,顺便复习了一下读入优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cassert>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
const int maxn=5050;
const int maxm=500050;
vector<int> e[maxm];
const int mod=80112002;
void addEdge(int u, int v) {
e[u].push_back(v);
}
int n, m, ans;
queue<int> q;
int ind[maxn], outd[maxn], ways[maxn];
int read() {
int x=0, val=1; char c=' ';
while(!isdigit(c)) {
if(c=='-') val=-1;
c=getchar();
}
while(isdigit(c)) {
x=x*10+c-'0';
c=getchar();
}
return x;
}
int main() {
n=read(); m=read();
for(int i=1; i<=m; i++) {
int u=read(), v=read();
addEdge(u, v);
outd[u]++; ind[v]++;
}
for(int i=1; i<=n; i++) {
if(!ind[i]) {
ways[i]=1;
q.push(i);
}
}
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=0; i<e[u].size(); i++) {
int v=e[u][i];
ways[v]=((ways[v]+ways[u])%mod+mod)%mod;
ind[v]--;
if(ind[v]==0) {
if(outd[v]==0) {
ans=((ans+ways[v])%mod+mod)%mod;
continue;
}
q.push(v);
}
}
}
printf("%d\n", ans);
return 0;
}

 评论



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:742.8k