最大路径权值
第一步
如果有环,那么环上的字母就会无限出现,那么权值将会无穷大
所以第一步先判断有没有环,注意是有向图,所以可以考虑用拓扑排序
第二步
根据题中给的要求,出现频率最高的字母
注意是字母!像遇到二进制和字母,都可以尝试枚举(一般出题人都不会卡你
我们把每个字母枚举,然后求出现枚举的这个字母的最大路权值即可
枚举时,我们把枚举的字母的点的权值设为1,其他为0
根据前面拓扑排序后,没有环,所以可以用dp
(为什么可以用,因为是有向图且没有环,天然满足dp的无后效性原则)
```
include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
int n,m;
const int maxn=3e5+10;
int head[maxn];
int f[maxn];
struct node{
int v,next;
}e[maxn];
string s;
int cnt=0;
void add(int u,int v){
e[cnt].v=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int q[maxn];
int in[maxn];//入度
bool topsort(){
int l=1,r=0;
for(int i=1;i<=n;i) if(in[i]==0) q[r]=i;
while(l<=r){
int u=q[l];
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;in[v]–;
if(in[v]==0) q[r]=v;
}l;
}
if(r==n) return 0;
return 1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
cin>>s;
for(int i=1;i<=m;i){
int u,v;cin>>u>>v;
add(u,v);in[v];
}
int res=0;
if(topsort()) puts(“-1”);//有环图
else {
for(char c=’a’;c<=’z’;c){
for(int i=1;i<=n;++i)//初始化
if(in[i]==0) f[i]=s[i-1]==c;
for(int i=1;i<=n;++i){//从前往后dp
int u=q[i];
for(int j=head[u];j;j=e[j].next){
int v=e[j].v;
int w=s[v-1]==c;
f[v]=max(f[v],w+f[u]);
res=max(res,f[v]);
}
}
}
cout<<res<<endl;
}
return 0;
}