我是靠谱客的博主 爱听歌御姐,这篇文章主要介绍Luogu P1137 旅行计划 【拓扑排序+Dp】By cellur925,现在分享给大家,希望可以做个参考。

题目传送门

由于满足游览先后顺序从西到东的性质,我们很自然的想到用拓扑排序处理出一个合理的游览顺序。

然鹅,之后呢?

事实上,拓扑排序常与Dp相结合,解决后效性。我们就可以在每次拓扑入队的时候更新答案,设f[i]表示终点为i能经过的最多城市数。则f[j]=max(f[j],f[i]+1).

 

*Update

思考的时候,没想到dp qwq. 知道要用dp后就想了很久,想出了记录前驱的方法,但是不太对。(挖坑)

code

复制代码
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
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 5 using namespace std; 6 7 int n,m,x,y,tot,cnt; 8 int head[100090],du[100090],f[100090]; 9 struct node{ 10 int next,to; 11 }edge[200090]; 12 13 void add(int x,int y) 14 { 15 edge[++tot].to=y; 16 edge[tot].next=head[x]; 17 head[x]=tot; 18 } 19 20 void topo() 21 { 22 queue<int>q; 23 for(int i=1;i<=n;i++) 24 if(!du[i]) q.push(i),f[i]=1; 25 while(!q.empty()) 26 { 27 int u=q.front();q.pop(); 28 for(int i=head[u];i;i=edge[i].next) 29 { 30 int v=edge[i].to; 31 f[v]=max(f[v],f[u]+1); 32 if(--du[v]==0) q.push(v); 33 } 34 } 35 } 36 37 38 int main() 39 { 40 scanf("%d%d",&n,&m); 41 for(int i=1;i<=m;i++) 42 scanf("%d%d",&x,&y),add(x,y),du[y]++; 43 topo(); 44 for(int i=1;i<=n;i++) 45 printf("%dn",f[i]); 46 return 0; 47 }
View Code

 

转载于:https://www.cnblogs.com/nopartyfoucaodong/p/9490443.html

最后

以上就是爱听歌御姐最近收集整理的关于Luogu P1137 旅行计划 【拓扑排序+Dp】By cellur925的全部内容,更多相关Luogu内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(57)

评论列表共有 0 条评论

立即
投稿
返回
顶部