题目描述：

给你n个字符串。

如果一个字符串的最后两个字符和另一个字符串的开头两个字符相同的话，那么这两个字符串可以连接。

现在让你连接成一个环（当然，每个字符串只能用一次）。

这个环的平均长度是：环中所有的字符串长度之和 除以 字符串的个数。

输出 最长 的平均长度。

如果不存在，输出 无解。

 

解题报告：

建图：

单词：intercommunicational

那么就连接in节点 和 al节点，权值为单词的长度。

问题就转化成了：

在图中找环，环的边权相加 除以 边数 就是这个环的平均长度。

 

但是怎样找到最长的呢？

二分！

注意到：

枚举每一个平均长度mid值。

如果存在一个环，(E1+...+Ek)/k>=mid(其中k是边数，E1……Ek是各个边权)，

那么正解比mid大，否则比mid小，这就是二分策略。

那么怎样知道是否存在(E1+...+Ek)/k>=mid 呢？

如下转化：(E1+...+Ek)>=mid*k

E1-mid + E2–mid + E3-mid + ... + Ek-mid >= 0

所以，把所有的边权改为Ei – mid，然后看是否存在正环就可以，存在就是满足条件。

 

代码如下：

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
#define size 700
#define eps 1e-8
int n, cnt[2];
double dis[size];
struct edge{int from, to; double val;} e[2][100005];
void insert(int from, int to, double va, int id)
{
    e[id][cnt[id]].from = from; e[id][cnt[id]].to = to; e[id][cnt[id]++].val = va;
}
char str[1001];
int judge(char a, char b)
{
    return (a - 'a') * 26 + b - 'a';
}
bool bellman()
{
    for(int i = 0; i < 676; i++) dis[i] = -1000000000;
    for(int i = 0; i < 676; i++)
    {
        bool flag = false;
        for(int j = 0; j < cnt[1]; j++)
            if (dis[e[1][j].from] + e[1][j].val > dis[e[1][j].to])
            {
                flag = true;
                dis[e[1][j].to] = dis[e[1][j].from] + e[1][j].val;
            }
        if (!flag) return false;
    }
    for(int j = 0; j < cnt[1]; j++)
        if (dis[e[1][j].from] + e[1][j].val > dis[e[1][j].to])
            return true;
    return false;
}
int main()
{
    while(scanf("%d", &n) && n)
    {
        cnt[0] = 0;
        double r = 0;
        for(int i = 0; i < n; i++)
        {
            scanf("%s", str);
            int len = strlen(str);
            r = max(r, (double)len);
            insert(judge(str[0], str[1]), judge(str[len - 2], str[len - 1]), (double)len, 0);
        }
        double l = 0;
        bool flag = false;
        while(r - l >= eps)
        {
            double mid = (r + l) * 0.5; cnt[1] = 0;
            //cout << mid << endl;
            for(int i = 0; i < cnt[0]; i++)
                insert(e[0][i].from, e[0][i].to, e[0][i].val - mid, 1);
            if (bellman()) {flag = true;l = mid;}
            else r = mid;
        }
        if (!flag) printf("No solution.\n");
        else
        printf("%.2f\n", l);
    }
}