题意：一个有向图，每个结点 被赋予一个小写字母，一条路径的value等与这条路径上出现次数最多的字母的数目，求该图的最大value
比赛时，用dfs超时，看官方题解用的dp和拓扑排序，a--z用0-25表示，用dp[i][j]表示以第i个结点结尾的路径上第j个字母出现的次数
拓扑排序每排到一个点，就用该点的dp去更新与它相邻点的dp，最开始入度为0的点特殊处理了一下，dp过程中同步更新结果res
也复习了一下拓扑排序
#include<iostream> #include<cstdio> #include<cstring> #include<vector> #include<queue> using namespace std; #define Nnum 300005 char ch[Nnum]; int dp[Nnum][26]; vector<int> eage[Nnum]; int deg[Nnum]; int n,m,res; bool deg0[Nnum]; bool toposort() { int cnt=0; queue<int> que; for(int i=1; i<=n; i++) if(deg[i]==0) { cnt++; que.push(i); deg0[i]=1; } else deg0[i]=0; while(!que.empty()) { int now=que.front(); que.pop(); if(deg0[now]==1) //最初入度为0的点，其dp需附上初值，再更新相邻结点 dp[now][ch[now-1]-'a']++; for(int i=0; i<eage[now].size(); i++) { for(int j=0; j<26; j++) { int tmp=ch[eage[now][i]-1]-'a'; if(j==tmp) dp[eage[now][i]][tmp]=max(dp[eage[now][i]][tmp],dp[now][tmp]+1); else dp[eage[now][i]][j]=max(dp[eage[now][i]][j],dp[now][j]); res=max(res,dp[eage[now][i]][j]); } //cout<<"*"<<res<<endl; deg[eage[now][i]]--; if(deg[eage[now][i]]==0) { que.push(eage[now][i]); cnt++; } } } if(cnt==n) return 1; else return 0; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<=n;i++) eage[i].clear(); res=0; memset(deg,0,sizeof(deg)); memset(dp,0,sizeof(dp)); scanf("%s",ch); for(int i=0; i<m; i++) { int a,b; scanf("%d%d",&a,&b); deg[b]++; eage[a].push_back(b); } if(toposort()) printf("%d ",res); else printf("-1 "); } return 0; }