单词环

题目描述：

我们有 n 个字符串，每个字符串都是由 a∼z 的小写英文字母组成的。

如果字符串 A 的结尾两个字符刚好与字符串 B 的开头两个字符相匹配，那么我们称 A 与 B 能够相连（注意：A 能与 B 相连不代表 B 能与 A 相连）。

我们希望从给定的字符串中找出一些，使得它们首尾相连形成一个环串（一个串首尾相连也算），我们想要使这个环串的平均长度最大。

思路：

二分答案 + SPFA判正环

在观光奶牛 和 E – Average and Median 的经验下，这个题的思路就很显然了

首先建图，朴素建图肯定不行，但是可以发现最多就是26 * 26个前缀和后缀，我们可以根据这个来建图

二分平均长度mid的时候，图中的边权就应该是c-mid，然后判断是否存在正环就行

注意，普通的SPFA过不去这个题，会被卡，但是可以用SLF优化

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 200000 + 50
int n, m, k;
char s[1005];

int tot;
int head[1005];
struct ran{
    int to, nex, val;
}tr[MAX];
inline void add(int u, int v, int c){
    tr[++tot].to = v;
    tr[tot].val = c;
    tr[tot].nex = head[u];
    head[u] = tot;
}

double dis[2005];
bool vis[2005];
int num[2005];
bool SPFA(double mid){
    deque<int>q;
    for(int i = 0; i < 676; ++i){
        q.push_back(i);
        num[i] = 0;
        dis[i] = 0;
        vis[i] = 1;
    }
    while (!q.empty()) {
        int u = q.front();q.pop_front();vis[u] = 0;
        for(int i = head[u]; i; i = tr[i].nex){
            int v = tr[i].to;
            if(dis[v] < dis[u] + tr[i].val - mid){
                dis[v] = dis[u] + tr[i].val - mid;
                num[v] = num[u] + 1;
                if(num[v] >= 676){
                    return true;
                }
                if(!vis[v]){
                    vis[v] = 1;
                    if(q.size() && dis[v] > dis[q.front()])q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
    return false;
}

void work(){
    while(scanf("%d",&n) != EOF && n){
        tot = 0;
        mem(head, 0);
        for(int i = 1; i <= n; ++i){
            scanf("%s", s);
            int a = (s[0] - 'a') * 26 + s[1] - 'a';
            int len = (int)strlen(s);
            int b = (s[len - 2] - 'a') * 26 + s[len - 1] - 'a';
            add(a, b, len);
        }
        double l = 0, r = 1000, eps = 1e-6;
        while (r - l >= eps) {
            double mid = (l + r) / 2;
            if(SPFA(mid))l = mid;
            else r = mid;
        }
        if(l == 0)printf("No solution\n");
        else printf("%.2f\n", l);
    }
}


int main(){
    work();
    return 0;
}