Substring

题目描述

传送门

题目大意

一个有$n$个点$m$条边的有向图，每个点有一个小写字母权值，定义一条路径的权值是这条路径出现次数最多的字母的个数，求出这个图权值最大权值的路径的权值。
$1\le n,m\le 300000$
PS : 若存在一条路径使得出现次数最多的字母数量为无穷大，则输出 -1，路径不要求为简单路径。

Solution

• 首先我们考虑一下什么时候要输出-1。
  发现之所以输出-1是因为有一条路径可以无限走下去，也就是有环。
• 一个合法的解是不存在环的，也就是说是一个TAG，于是我们选择进行拓扑排序，既解决了判断是否合法的问题，还得出了拓扑序为接下来的工作做准备。
• 我们设$f[i][26]$为以第$i$个节点为起点的路径，每种字母出现的最多的次数，之后倒着跑一遍DP即可。

附上代码 ：

#include<cstdio>
#include<algorithm>
#include<queue>
const int maxn = 300007;
class Solution{
private :
char s[maxn];
int n, m, in[maxn], p[maxn], cnt;
int f[maxn][26], ans;
bool vis[maxn], flag;
std :: vector<int> to[maxn], back[maxn];
std :: queue<int> q;
void TopoSort() {
while (!q.empty()) {
q.pop();
}
for (register int i = 1; i <= n; i++) {
if (!in[i]) {
q.push(i);
}
}
while (!q.empty()) {
int now = q.front();
q.pop();
p[++cnt] = now;
for (register std :: vector<int> :: iterator i = to[now].begin(); i != to[now].end(); ++i) {
int v = *i;
in[v]--;
if (!in[v]) {
q.push(v);
}
}
}
if (cnt != n) {
flag = 1;
}
}
public :
Solution() {
Get();
Solve();
}
void Get() {
scanf("%d %d", &n, &m);
scanf("%s", s + 1);
for (register int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
to[u].push_back(v);
in[v]++;
}
}
void Solve() {
TopoSort();
if (flag) {
printf("-1n");
return;
}
for (register int i = n; i >= 1; i--) {
int now = p[i];
for (register std :: vector<int> :: iterator j = to[now].begin(); j != to[now].end(); ++j) {
int v = *j;
for (register int k = 0; k < 26; k++) {
f[now][k] = std :: max(f[now][k], f[v][k]);
}
}
f[now][s[now] - 'a']++;
ans = std :: max(ans, f[now][s[now] - 'a']);
}
printf("%dn", ans);
}
};
Solution sol;
int main() {}

最后

以上就是和谐火龙果为你收集整理的CF919D SubstringSubstring的全部内容，希望文章能够帮你解决CF919D SubstringSubstring所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。