cf919D 线性dp+拓扑排序

/* 给定一张有向图，图上每个结点都有一个字符，现在要求出一条路径，要使路径上某字符出现的次数最多 如果有环，输出-1即可 拓扑排序+dp dp[i][26]表示排序到结点i时26个字符出现的次数 在每次访问到i时都进行dp */ #include<bits/stdc++.h> using namespace std; #define maxn 300005 struct Edge{int to,nxt;}edge[maxn<<1]; int head[maxn],tot,n,m,ans; char a[maxn]; void init(){ memset(head,-1,sizeof head); tot=0; } void addedge(int u,int v){ edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++; } int in[maxn],dp[maxn][26]; int main(){ init(); cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; addedge(u,v); in[v]++; } queue<int>q;ans=1; int cnt=0; for(int i=1;i<=n;i++) if(in[i]==0){ q.push(i); dp[i][a[i]-'a']++; } while(!q.empty()){ int u=q.front();q.pop(); cnt++; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; in[v]--; for(int j=0;j<26;j++) dp[v][j]=max(dp[v][j],dp[u][j]); if(in[v]==0){ q.push(v); dp[v][a[v]-'a']++; } } } if(cnt<n)puts("-1"); else { for(int i=1;i<=n;i++) for(int j=0;j<26;j++) ans=max(ans,dp[i][j]); cout<<ans<<endl; } return 0; }

 

转载于:https://www.cnblogs.com/zsben991126/p/10473043.html