題目描述

You are given a graph with?nn?nodes and?mm?directed edges. One lowercase letter is assigned to each node. We define a path's value as the number of the most frequently occurring letter. For example, if letters on a path are "abaca", then the value of that path is?33?. Your task is find a path whose value is the largest.

輸入輸出格式

輸入格式：

?

The first line contains two positive integers?n,mn,m?(?1<=n,m<=3000001<=n,m<=300000?), denoting that the graph has?nn?nodes and?mmdirected edges.

The second line contains a string?ss?with only lowercase English letters. The?ii?-th character is the letter assigned to the?ii?-th node.

Then?mm?lines follow. Each line contains two integers?x,yx,y?(?1<=x,y<=n1<=x,y<=n?), describing a directed edge from?xx?to?yy?. Note that?xx?can be equal to?yy?and there can be multiple edges between?xx?and?yy?. Also the graph can be not connected.

?

輸出格式：

?

Output a single line with a single integer denoting the largest value. If the value can be arbitrarily large, output -1 instead.

?

輸入輸出樣例

輸入樣例#1：?
5 4 abaca 1 2 1 3 3 4 4 5 輸出樣例#1：?
3 輸入樣例#2：?
6 6 xzyabc 1 2 3 1 2 3 5 4 4 3 6 4 輸出樣例#2：?
-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 輸出樣例#3：?
4

說明

In the first sample, the path with largest value is?1→3→4→51→3→4→5?. The value is?33?because the letter 'a' appears?33?times.

?

XJB DP就行了，之前判一下是不是DAG

?

#include<iostream> #include<cmath> #include<algorithm> #include<cstdlib> #include<cstdio> #include<cstring> #include<vector> #include<queue> #define ll long long #define maxn 300005 using namespace std; int ans=0,g[maxn]; int n,m,id[maxn],u,v; int f[maxn],hd[maxn]; int to[maxn],ne[maxn]; bool vis[maxn]; char s[maxn];inline int num(char x){return x-'a'; }inline bool topsort(){queue<int> q;int x,tot=0;for(int i=1;i<=n;i++) if(!id[i]) q.push(i);while(!q.empty()){x=q.front(),q.pop(),tot++;for(int i=hd[x];i;i=ne[i]) if(!(--id[to[i]]))q.push(to[i]);}return tot==n; }int dp(int x){if(vis[x]) return g[x];vis[x]=1,g[x]=0;for(int i=hd[x];i;i=ne[i]) g[x]=max(g[x],dp(to[i]));g[x]+=f[x];return g[x]; }int main(){scanf("%d%d",&n,&m);scanf("%s",s+1);for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);to[i]=v,ne[i]=hd[u];hd[u]=i,id[v]++;}if(!topsort()){puts("-1");return 0;}for(int i=0;i<26;i++){memset(vis,0,sizeof(vis));for(int j=1;j<=n;j++) f[j]=(num(s[j])==i);for(int j=1;j<=n;j++) ans=max(ans,dp(j));}printf("%d\n",ans);return 0;}

　　

轉(zhuǎn)載于:https://www.cnblogs.com/JYYHH/p/8474694.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces 919 D Substring的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。