D. Substring
题目描述
给定一个包含 n 个节点和 m 条有向边的图，每个节点上都有一个小写英文字母。
我们定义一条路径的价值为：该路径上出现次数最多的字母的出现次数。
例如，一条路径上的字母依次为 abaca，其中字母 a 出现了 3 次，因此这条路径的价值为 3。
请你求出价值最大的路径。
如果答案可以无限大，则输出 -1。
输入格式
第一行包含两个正整数 n,m：
$1\le n,m\le 300000$
分别表示图中的节点数量和有向边数量。
第二行包含一个长度为 n 的字符串 s，其中只包含小写英文字母。字符串中的第 i 个字符表示第 i 个节点上的字母。
接下来 m 行，每行包含两个整数 x,y：
$1\le x,y\le n$
表示存在一条从节点 x 指向节点 y 的有向边。
需要注意：
- x 可以等于 y，即图中可能存在自环；
- 节点 x 和节点 y 之间可能存在多条相同的边；
- 整张图不一定连通。
输出格式
输出一个整数，表示所有路径中的最大价值。
如果路径的价值可以无限增大，则输出：
-1
样例 #1
输入
5 4
abaca
1 2
1 3
3 4
4 5
输出
3
说明
价值最大的路径为：
$1\rightarrow3\rightarrow4\rightarrow5$
这条路径上的字母依次为 aaca，其中字母 a 出现了 3 次，因此路径的价值为 3。
样例 #2
输入
6 6
xzyabc
1 2
3 1
2 3
5 4
4 3
6 4
输出
-1
样例 #3
输入
10 14
xzyzyzyzqx
1 2
2 4
3 5
4 5
2 6
6 8
6 5
2 10
3 9
10 9
4 6
1 10
2 8
3 7
输出
4
数据范围
$1\le n,m\le 300000$
时间限制：$3$ 秒。
空间限制：$256\ \text{MB}$。
思路
这是一道dp+图论的题
如果图中存在有向环，就可以沿着环移动，由于环上至少有一个字母，所以这个字母出现的次数可以无限增加，答案为-1。
定义
dp[c][u]
dp一维是代表26个英文字母，二维是每个节点
首先加入入度为0的节点就是拓扑起点，然后从根节点开始向下dp，先转移状态，然后下一个节点要加上这个节点上面的字母
状态转移方程dp[c][v]=max(dp[c][v],dp[c][u]+[sv=c])
如果这个节点出队并且完成处理，就要加入cnt，如果cnt!=n，那么就说明有环，也就输出-1，否则输出ans统计最大的重复字母。
代码
//Sunshine sunshine ladybugs awake,
//Clap your hooves and do a little shack.
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
using PII=pair<int,int> ;
const int MAXN=300005;
const int mod=998244353;
const int INF=0x3f3f3f3f3f3f3f3f;
vector<int> adj[MAXN];
vector<int> deg(MAXN,0);
int dp[26][MAXN];
string s;
void solve(){
int n,m;
cin>>n>>m;
cin>>s;
for(int i=0;i<m;i++){
int u,v;
cin>>u>>v;
adj[u].push_back(v);
deg[v]++;
}
int cnt=0;
int ans=0;
queue<int> q;
for(int u=1;u<=n;u++){
dp[s[u-1]-'a'][u]=1;
if(deg[u]==0){
q.push(u);
}
}
while(!q.empty()){
int u=q.front();
q.pop();
cnt++;
for(int c=0;c<26;c++){
ans=max(ans,dp[c][u]);
}
for(auto v:adj[u]){
for(int c=0;c<26;c++){
dp[c][v]=max(
dp[c][v],
dp[c][u]+(s[v-1]-'a'==c)
);
}
deg[v]--;
if(deg[v]==0)q.push(v);
}
}
if(cnt<n){
cout<<-1<<endl;
}else{
cout<<ans<<endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//int t;cin>>t;while(t--)
solve();
return 0;
}
