Word Rings

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2087 字
二分答案加DFS版SPFA判正环
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1504
// 题意：多组数据，每组给 n 个串，前串后两字符等于后串前两字符即可相接；求能首尾成环时的最大平均长度，无解输出 No solution。
// 思路：把每个串压成「前两字符 -> 后两字符」的边，边权为串长，二分答案后用 DFS 版 SPFA 判是否存在平均长度超过 mid 的正环。
// 1. 节点只有 26 * 26 = 676 个，边权减去 mid 后判正环即可。
// 2. 多组数据以 0 结束，每组要清空邻接表。
// 复杂度：O(676 * n * log V) 时间 / O(676 + n) 空间
// 易错点：二分的是「是否存在正环」，有环则把下界抬上去，不要把方向写反。
// 易错点：串长可能只有 2，此时首尾两字符下标相同，要照常建自环边。
// 易错点：标准输出是截断两位小数（21.666... 输出 21.66），直接四舍五入会得到 21.67。
#include <bits/stdc++.h>
using namespace std;
const int V = 676;
struct Edge{
    int to;
    int w;
};
vector<Edge> g[V];
double dis[V];
bool instk[V];
bool dfs(int u, double mid){
    instk[u] = true;
    for(int i = 0; i < (int)g[u].size(); i++){
        int v = g[u][i].to;
        double w = (double)g[u][i].w - mid;
        if(dis[v] < dis[u] + w){
            dis[v] = dis[u] + w;
            if(instk[v]) return true;
            if(dfs(v, mid)) return true;
        }
    }
    instk[u] = false;
    return false;
}
bool check(double mid){
    for(int i = 0; i < V; i++){
        dis[i] = 0.0;
        instk[i] = false;
    }
    for(int i = 0; i < V; i++){
        if(dfs(i, mid)) return true;
    }
    return false;
}
int main(){
    int n;
    while(cin >> n){
        if(n == 0) break;
        for(int i = 0; i < V; i++){
            g[i].clear();
        }
        for(int i = 0; i < n; i++){
            string s;
            cin >> s;
            int len = (int)s.size();
            int a = (s[0] - 'a') * 26 + (s[1] - 'a');
            int b = (s[len - 2] - 'a') * 26 + (s[len - 1] - 'a');
            Edge e;
            e.to = b;
            e.w = len;
            g[a].push_back(e);
        }
        double lo = 0.0;
        double hi = 1000.0;
        for(int it = 0; it < 40; it++){
            double mid = (lo + hi) / 2.0;
            if(check(mid)) lo = mid;
            else hi = mid;
        }
        if(lo < 1e-9){
            cout << "No solution" << "\n";
        }else{
            double out = floor(lo * 100.0 + 1e-9) / 100.0;
            cout << fixed << setprecision(2) << out << "\n";
        }
    }
    return 0;
}
Word Rings

正文

一本通·提高篇的其它内容
