正題

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

---

題目大意

一個輛車會一個一個值$x$，如果等級大于等于$x$的車站都會停靠(包括起點和終點)。給每輛車的停靠點，求至少要將車站分多少級。

---

解題思路

對于一輛車，若一個點他經過了卻沒有停靠，那么這個點比所有的停靠點的等級都要低。然后根據這個關系連邊，然后記憶化$dfs$。時間復雜度$O(n{m}^2)$，邊比較多，建議用鄰接矩陣。但是是$\frac{1}{4}$常數，所以可以過。

可以優化成$O(nm)$的。對于沒輛車，我們的邊數是$O(nm)$條的密集圖，所以我們可以建立一個虛點，然后將邊數變為$O(n+m)$條。

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=1050; int ans,n,m,a[2*N][2*N],f[N]; bool v[N]; int dfs(int x){if(f[x]) return f[x];for (int i=1;i<=n+m;i++) if(a[x][i]) f[x]=max(f[x],dfs(i));if(x>n) f[x]--;return ++f[x]; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int t,x,star,end;memset(v,0,sizeof(v));scanf("%d",&t);for(int j=1;j<=t;j++){scanf("%d",&x);a[x][n+i]=1;v[x]=1;if(j==1) star=x;if(j==t) end=x;}for(int j=star;j<=end;j++){if(v[j]) continue;a[n+i][j]=1;}}for(int i=1;i<=n;i++)ans=max(ans,dfs(i));printf("%d",ans); }

總結

以上是生活随笔為你收集整理的P1983-车站分级【图论,记忆化dfs,构图】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。