AcWing 周赛13 3813. 最大路径权值(拓扑排序 DAG上dp)

AcWing 周赛13 3813. 最大路径权值(拓扑排序 DAG上dp)

​​原题链接​​

题意：

思路：

代码：

const int maxn=3e5+100;vectorg[maxn];int n,m,dp[maxn][28],din[maxn];char s[maxn];int topsort(){ queueq; int siz=0; rep(i,1,n) if(din[i]==0){ q.push(i); dp[i][s[i]-'a']=1; siz++; } while(!q.empty()){ int t=q.front();q.pop(); for(auto v:g[t]){ rep(i,0,25){ int tt=0; if(i==s[v]-'a') tt++; dp[v][i]=max(dp[v][i],dp[t][i]+tt); } if(--din[v]==0) q.push(v),siz++; } } rep(i,1,n) if(din[i]>0) return -1; int ans=0; rep(i,1,n) if(g[i].size()==0){ rep(j,0,25) ans=max(ans,dp[i][j]); } return ans;}int main(){ n=read,m=read; scanf("%s",s+1); rep(i,1,m){ int u=read,v=read; din[v]++; g[u].push_back(v); } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。