Luogu P1137 旅行计划【拓扑排序+Dp】By cellur925

53 阅读 0 评论 35 点赞

我是靠谱客的博主爱听歌御姐，最近开发中收集的这篇文章主要介绍Luogu P1137 旅行计划【拓扑排序+Dp】By cellur925，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目传送门

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

然鹅，之后呢？

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

*Update

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

code

 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 }