P4017 最大食物链计数
首先确定通过拓扑排序来解决问题，要找到最长的食物链，就要明确食物链的长度如何确定。
从入度为 0 的点开始，到达一个出度为 0 的点之后，确定一条食物链。
最终答案是将所有链的长度加合到一起，记得开 longlong 和 取模。
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6, MOD = 80112002;
int n,m,in[N],out[N],ans,vis[N],a[N];
vector<int>g[N];
void TopoSort(){
queue<int>s;
ans=0;
for(int i=1;i<=n;i++){
if(!in[i]){
vis[i]=1;
s.push(i);
}
}
while(!s.empty()){
int u = s.front();
s.pop();
for(auto v:g[u]){
vis[v]=vis[v]+vis[u]%MOD;
if(--in[v]==0){
s.push(v);
}
}
}
for(int i=1;i<=n;i++){
if(!out[i])ans=ans+vis[i]%MOD;
}
cout<<ans%MOD<<endl;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
out[u]++,in[v]++;
}
TopoSort();
return 0;
}
|
P2712 摄像头
本题是直播中的例题
只能砸当前没被监视到的，那我们就 S 中有多少个能进来的元素，因为进 S 中的元素都是入度为 0 的元素。
坑点在于给的数据不一定连续，即可能有 3 个摄像头，但是给的摄像头对应位置是 1,3,5 这种，不能按顺序进行，要用数组来储存对应位置，并记录某些位置是否有摄像头，因为一些摄像头也可能监视到不存在摄像头的位置。
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
|
#include <bits/stdc++.h>
using namespace std;
int n,m,in[10001],ans,vis[10001],a[10001];
vector<int>g[10001];
void TopoSort(){
queue<int>s;
ans=0;
for(int i=1;i<=n;i++){
if(!in[a[i]] && vis[a[i]])
s.push(a[i]);
}
while(!s.empty()){
int u = s.front();
ans++;
s.pop();
for(auto v:g[u]){
if(--in[v]==0&&vis[v])s.push(v);
}
}
if(ans==n)cout<<"YES\n";
else cout<<n-ans<<endl;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int m;
cin>>a[i]>>m;
vis[a[i]]=1;
for(int j=1;j<=m;j++){
int y;
cin>>y;
g[a[i]].push_back(y);
in[y]++;
}
}
TopoSort();
return 0;
}
|
P6145 [USACO20FEB] Timeline G
首先看到题目，当然要明白它究竟想要干什么。
题目描述的方式很像一个 DAG，于是把每次挤奶看做一个节点，每次挤奶的间隔天数 $x$ 当做边权，从 $a$ 到 $b$ 连边。
至于 $S_i$，可以看做是第 $0$ 次挤奶后，间隔 $S_i$ 天后，再进行后面的挤奶。
实际建图中我们无需新建 $0$ 号节点，因为我们直接用 $S_i$ 递推就行，相当于已经遍历过这些边。
然后根据题意，不难得到一个节点的 $S_i$ 只能由它的前驱或者节点 $0$ 得到。后者其实就是输入时的 $S_i$。
题目要求的是"最早"，实际上要同时满足两个限制（分别为输入时的 $S_i$ 和三元组），我们只能选日期更后的，并为了使其最小，就让它刚好等于那个更后的日期。显然，递推式为：
$S_i = \max{S_i, S_{pre}+v}$
其中 $pre$ 是 $i$ 的前驱节点，$v$ 是连接这两个点的边权。
用拓扑排序求出前驱节点并递推即可。
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
|
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1e6, MOD = 80112002;
int n,m,c,in[N],vis[N],ans[N];
vector<pair<int,int>>g[N];
void TopoSort(){
queue<int>s;
for(int i=1;i<=n;i++){
if(!in[i]){
s.push(i);
}
}
while(!s.empty()){
int u = s.front();
s.pop();
if(vis[u])continue;
vis[u]=1;
for(auto [v,x]:g[u]){
ans[v]=max(ans[v],ans[u]+x);
if(--in[v]==0){
s.push(v);
}
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
}
signed main(){
cin>>n>>m>>c;
for(int i=1;i<=n;i++)cin>>ans[i];
for(int i=1;i<=c;i++){
int u,v,x;
cin>>u>>v>>x;
g[u].push_back({v,x});
in[v]++;
}
TopoSort();
return 0;
}
|
P1960 郁闷的记者
首先确定，没有输过的队伍一定是第一个输出的，如果这种队伍不只一个，那么就有多种排序方案了。
接着只要正常拓扑即可得到答案。
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
|
#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int N = 1e6, MOD = 80112002;
int n,m,in[N],vis,ans[N];
vector<int>g[N];
void TopoSort(){
queue<int>s;
for(int i=1;i<=n;i++){
if(!in[i]){
s.push(i);
}
}
if(s.size()>1)vis=1;
while(!s.empty()){
int u = s.front();
cout<<u<<endl;
int tmp=0;
s.pop();
for(auto v:g[u]){
if(--in[v]==0){
s.push(v);
tmp++;
}
}
if(tmp>1)vis=1;
}
cout<<vis<<endl;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
g[u].push_back(v);
in[v]++;
}
TopoSort();
return 0;
}
|