题意：给你一些单词，如果一个单词的后两个字母和另外一个单词的前两个字母一样，那么这两个单词就可以连在一起，然后让你求单词成环之后，最大的平均权值。

解法：求平均权值最大的环路？ 记得一本书上说过，假如所有的边都在环中，其实就是:E1+E2+E3+E4+....+En = mid*n;转换一下即为：E1-mid+E2-mid+...En-mid = 0;这是权值相等的时候。 要使得mid最大，那么我们可以把E1-mid做为原先图的边。如果有正环存在，说明权值可以继续增大。 二分枚举mid即可。

要用stack来进行入队、出队操作才可以过，要不是会TLE。原因在一篇论文集上有所说明，我认为只需掌握怎么写就行了。

#include <iostream>       
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
using namespace std;

int k, n, m;

const int maxn = 2010;
const int maxm = 1010*1010*2;
const int INF = 0x3f3f3f3f;

double d[maxn];

struct Edge
{
	int u, v;
	double w;
	int next;
}edge[maxm];

int cnt;
int first[maxn];

void read_graph(int u, int v, double w)
{
	edge[cnt].v = v, edge[cnt].w = w;
	edge[cnt].next = first[u], first[u] = cnt++;
}

bool inq[maxn];

double L, R;

int spfa(double mid)
{
	stack<int> Q;
	for(int i = 1; i <= k; i++)
	{
		d[i] = 0;
		Q.push(i);
		inq[i] = 1;
	}
	
	int CNT[maxn] = {0};
	while(!Q.empty())
	{
		int x = Q.top(); Q.pop();
		inq[x] = 0;
		for(int e = first[x]; e != -1; e = edge[e].next)
		{
			int v = edge[e].v;
			double w = edge[e].w;
			if(d[v] < d[x]+w)
			{
				d[v] = d[x]+w;
				if(!inq[v])
				{
					inq[v] = 1;
					if(++CNT[v] > k) return 1;
					Q.push(v);
				}
			}
		}
	}
	return 0;
}

void init()
{
	cnt = 0;
	memset(first, -1, sizeof(first));
}

int ord(char x, char y)
{
    return (x-'a')*26+y-'a'+1;
}

int have_cycle(double mid)
{
	for(int i = 0; i < m; i++) edge[i].w -= mid;
	
	int flag = 0;
	if(spfa(mid)) flag = 1;
	
	for(int i = 0; i < m; i++) edge[i].w += mid;
	return flag;
}

const double eps = 1e-2;

char word[1010];

int vis[3010];

int main()
{
	while(scanf("%d", &m))
	{
		if(!m) break;
		init();
		
		memset(vis, 0, sizeof(vis));    
		L = 0, R = 0;
		
		k = 0;
		for(int i = 0; i < m; i++)
		{
			scanf("%s", word);
			int len = strlen(word);
			int a = ord(word[0], word[1]);
        	int b = ord(word[len-2], word[len-1]);
        	if(!vis[a]) vis[a] = ++k;
        	if(!vis[b]) vis[b] = ++k;
        	R = max(R, len*1.0);
        	read_graph(vis[a], vis[b], len*1.0);
		}
		
		double ans = -1;
		
		while(R-L >= eps)
		{
			double mid = L+(R-L)/2.0;
			if(have_cycle(mid))
			{
				ans = mid;
				L = mid;
			}
			else R = mid;
		}
		if(ans == -1) printf("No solution.\n");
		else printf("%.2f\n", ans);
	}
	return 0;
}