CF 919 D. SubstringD. Substring

D. Substring

链接

题意：

　　在一张有向图中，定义路径的权值为路径中出现次数最多的字符出现的次数，求一条权值最大的路径。如果权值可以无限大，输出-1。

分析：

　　注意是一张有向图。如果存在环那么输出-1，否则枚举字符，dp一下。

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
inline int read() {
int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 300005;
struct Edge { int to, nxt; } e[N];
int f[N], head[N], deg[N], q[N], d[N], En;
char s[N];
bool vis[N];
void add_edge(int u,int v) {
++En; e[En].to = v, e[En].nxt = head[u]; head[u] = En;
deg[v] ++;
}
int main() {
int n = read(), m = read();
scanf("%s", s + 1);
for (int i = 1; i <= m; ++i) {
int u = read(), v = read();
add_edge(u, v);
}
int L = 1, R = 0;
for (int i = 1; i <= n; ++i) {
d[i] = deg[i];
if (!deg[i]) q[++R] = i;
}
while (L <= R) {
int u = q[L ++];
vis[u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!(--d[v])) q[++R] = v;
}
}
for (int i = 1; i <= n; ++i)
if (!vis[i]) { puts("-1"); return 0; }
int ans = 0;
for (int c = 'a'; c <= 'z'; ++c) {
L = 1, R = 0;
for (int i = 1; i <= n; ++i) {
f[i] = 0;
d[i] = deg[i];
if (!deg[i]) {
q[++R] = i;
if (s[i] == c) f[i] = 1;
}
}
while (L <= R) {
int u = q[L ++];
ans = max(ans, f[u]);
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
f[v] = max(f[v], f[u] + (s[v] == c)); // !!!
if (!(--d[v])) q[++R] = v;
}
}
}
cout << ans;
return 0;
}