51Nod-3188 字符王国 题解

字符王国

题目大意

一个有向无环图，每个节点有一个字符

路径的枯燥度定义为：这条路径上字符出现次数最多的字符出现的次数

求最枯燥的路径的枯燥度

解题思路1

深搜+dp

$dp_{i,j}$表示第$i$个节点出发的路径中，字符$j$出现的最多的次数

对所有入度为0的节点做一次dfs（从越早的节点出发结果可能会越大，所以起点只考虑入度为0的点）

对节点$i$的每个子节点搜索完毕后，更新从$i$节点出发的所有字符的出现次数

最后求一次最大值即可

AC代码1

#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int N = 3e5 + 5;
int n, m;
string s;
vector<int> mp[N];
int indeg[N];

int ans = 0;
int cnt[N]['z' + 10];
bool vis[N];

void dfs(int x) {
    if (vis[x]) return;
    vis[x] = true;
    for (int i = 0; i < mp[x].size(); i++) {
        dfs(mp[x][i]);
        for (int j = 'a'; j <= 'z'; j++) {
            cnt[x][j] = max(cnt[x][j], cnt[mp[x][i]][j]);
        }
    }
    cnt[x][s[x - 1]]++;
}
int main() {
    #ifdef LOCAL
        freopen("D:/Code/ACM/in.in", "r", stdin);
        freopen("D:/Code/ACM/out.out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> s;
    while (m--) {
        int u, v;
        cin >> u >> v;
        mp[u].emplace_back(v);
        indeg[v]++;
    }
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            dfs(i);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 'a'; j <= 'z'; j++) {
            ans = max(ans, cnt[i][j]);
        }
    }
    cout << ans << "\n";
    return 0;
}

解题思路2

枚举每个字符，结果即为该字符出现最多的路径

建立超级源点和超级汇点，对每个字符跑一次最长路即可，最大的结果即为答案

如果一条边到达节点为该字符，该边权记录为1，否则为0

AC代码2

#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int N = 3e5 + 5;
const int INF = 0x3f3f3f3f;
int n, m;
string s;
vector<int> mp[N];
int indeg[N];
int outdeg[N];

int ans = 0;
int d[N];
struct cmp {
    bool operator() (int a, int b) {
        return d[a] < d[b];
    }
};

int dijkstra(char ch) {
    memset(d, -1, sizeof(d));
    priority_queue<int, vector<int>, cmp> q;
    q.push(0);
    d[0] = 0;
    while (q.size()) {
        auto x = q.top();   q.pop();
        for (int i = 0; i < mp[x].size(); i++) {
            int to = mp[x][i];
            int dist = s[mp[x][i] - 1] == ch ? 1 : 0;
            if (d[to] < d[x] + dist) {
                d[to] = d[x] + dist;
                q.push(to);
            }
        }
    }
    return d[n + 1];
}

int main() {
    #ifdef LOCAL
        freopen("D:/Code/ACM/in.in", "r", stdin);
        freopen("D:/Code/ACM/out.out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> s;
    while (m--) {
        int u, v;
        cin >> u >> v;
        mp[u].emplace_back(v);
        indeg[v]++;
        outdeg[u]++;
    }
    for (int i = 1; i <= n; i++) {
        if (indeg[i] == 0) {
            mp[0].emplace_back(i);
        }
        if (outdeg[i] == 0) {
            mp[i].emplace_back(n + 1);
        }
    }
    for (int i = 'a'; i <= 'z'; i++) {
        ans = max(ans, dijkstra(i));
    }
    cout << ans << "\n";
    return 0;
}