正題

題目鏈接:https://www.luogu.org/problemnew/show/P1137

---

題目大意

一張有向無環(huán)圖，求以每個點為終點的最長路徑。

---

解題思路

先拓撲排序，然后$dp$
$$f_y=max\{f_x+1\}(x?>y)$$

---

$code$

#include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int maxv=110000,maxe=210000; struct rec{int x,y,next; }a[maxe]; int n,e; int ls[maxv],in[maxv],list[maxv],f[maxv]; queue<int>q; void init() {scanf("%d%d",&n,&e);memset(ls,0,sizeof(ls));for(int i=1;i<=e;i++){scanf("%d%d",&a[i].x,&a[i].y);a[i].next=ls[a[i].x];ls[a[i].x]=i;} } void topsort(){int cnt=0;memset(in,0,sizeof(in));for(int i=1;i<=e;i++)in[a[i].y]++;for(int i=1;i<=n;i++)if(!in[i])q.push(i);while(!q.empty()){int x=q.front();q.pop();list[++cnt]=x;for(int i=ls[x];i;i=a[i].next){int y=a[i].y;in[y]--;if(!in[y])q.push(y);}} } void dp() {for(int i=1;i<=n;i++){int x=list[i];for(int i=ls[x];i;i=a[i].next){int y=a[i].y;f[y]=max(f[x]+1,f[y]);}} } void print(){for(int i=1;i<=n;i++)printf("%d\n",f[i]+1); } int main() {init();topsort();dp();print(); }

總結(jié)

以上是生活随笔為你收集整理的P1137-旅行计划【拓扑排序,DAGdp】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。