Codeforces 467D Fedor and Essay：BFS 最優替換傳播

Codeforces 467D Fedor and Essay：BFS 最優替換傳播

給定文章單詞列表及 M 條單向替換規則 (可將單詞 A 替換為 B)，目標使最終文章中字母 'r' 總數最少，若相同則總長度最短。不區分大小寫。

建模：有向圖 + 多源 BFS

• 節點：所有出現的單詞 (統一轉小寫)。
• 邊：替換規則 A→B 建邊 B→A (反向)，表示從 B 可「反向傳播」優勢到 A。
• 權值：(r_cnt, len)，按字典序比較 (先比 r_cnt，再比 len)。
• 初始：每個單詞自身權值為起始優勢。
• BFS：從所有節點入隊，若鄰居權值 > 當前權值，更新並入隊。類似 SPFA 求最優路徑。

算法正確性

反向邊保證若 B 可替換為 A，則 A 的優勢可傳播給 B。BFS 持續鬆弛直到無更新，得到每個單詞可達到的全局最優權值。

C++ 實現

#include 
using namespace std;
using pii = pair;
const int MAXN = 300005;

map id;
vector g[MAXN];
pii val[MAXN];
int word_id[MAXN];

int get_id(string &s) {
    for (char &c : s) if (c>='A' && c<='Z') c = c-'A'+'a';
    if (!id.count(s)) {
        int cnt_r = count(s.begin(), s.end(), 'r');
        id[s] = id.size();
        val[id[s]] = {cnt_r, (int)s.size()};
    }
    return id[s];
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        string s; cin >> s;
        word_id[i] = get_id(s);
    }
    int m; cin >> m;
    for (int i = 0; i < m; i++) {
        string a, b; cin >> a >> b;
        int u = get_id(a), v = get_id(b);
        g[v].push_back(u); // 反向邊
    }
    queue q;
    vector inq(id.size(), true);
    for (int i = 0; i < (int)id.size(); i++) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int v : g[u]) {
            if (val[v] > val[u]) {
                val[v] = val[u];
                if (!inq[v]) { q.push(v); inq[v] = true; }
            }
        }
    }
    long long total_r = 0, total_len = 0;
    for (int i = 0; i < n; i++) {
        total_r += val[word_id[i]].first;
        total_len += val[word_id[i]].second;
    }
    cout << total_r << ' ' << total_len << '\n';
    return 0;
}

關鍵點

• 反向建邊 + 多源 BFS (SPFA) 求最優傳播。
• 權值用 pair 自動實現字典序比較。
• 大小寫統一轉小寫處理。