首先就是如何建图?
假如把字符串作为点,那么连边的时候需要判断n * (n - 1)条边来连边,显然会爆掉
因此必须考虑其它方法
假如我们考虑把字符串的左右端点作为点,那么最多有26*26 = 676个点,边自然最多就是1e5
这个数量级还是可以做的,因此我们按照这个方式建图
然后如何解决->环串的平均长度最大?
按照上述方式建图,我们的边权自然就是字符串的长度
那么就是要使得 (环上边权之和)/ (边的数目) 这个值最大
那这就是一个01分数规划问题了,把式子稍加变形转化成二分判断正(负)环问题
超时?
SPFA判断负环超时的时候,可以做一个特判
当被更新的边超过边的总数目的数(2)倍时,我们可以认为图中有很大几率存在负环
或者直接把队列换成栈(只针对找正(负)环问题), 找指定环的效率会有所提高
建议使用scanf,效率更高!
解决上述三个问题,终于AC啦!
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 700, M = 1e5 + 10;
int h[N], e[M], ne[M], w[M], idx;
int cnt[N], q[N];
double dist[N];
bool st[N];
int n;
void add(int a, int b, int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++;
}
bool check(double mid)
{
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
int hh = 0, tt = 0;
for(int i = 0 ; i < 676 ; i ++)
{
q[tt ++] = i;
st[i] = true;
}
int count = 0;
while(hh != tt)
{
int t = q[hh ++];
// t = q[-- tt]; 换成栈的方式
if(hh == N) hh = 0; //用栈的情况下,该行可以去除
st[t] = false;
for(int i = h[t] ; ~i ; i = ne[i])
{
int j = e[i];
if(dist[j] < dist[t] + w[i] - mid)
{
dist[j] = dist[t] + w[i] - mid;
cnt[j] = cnt[t] + 1;
if(++ count > n * 2) return true; //用栈的情况下、去掉该行,保证正确性
if(cnt[j] >= N) return true;
if(!st[j])
{
q[tt ++] = j;
if(tt == N) tt = 0; //用栈的情况下,该行可以去除
st[j] = true;
}
}
}
}
return false;
}
int main()
{
while(cin >> n, n)
{
memset(h, -1, sizeof h);
idx = 0;
for(int i = 0 ; i < n ; i ++)
{
string s;
cin >> s;
int len = s.length();
int a = (s[0] - 'a') * 26 + s[1] - 'a';
int b = (s[len - 2] - 'a') * 26 + s[len - 1] - 'a';
add(a, b, len);
}
if(!check(0)) puts("No solution");
else
{
double l = 0, r = 1000;
while(r - l > 1e-4)
{
double mid = (l + r) / 2.0;
if(check(mid)) l = mid;
else r = mid;
}
cout << r << endl;
}
}
return 0;
}
佬,这里的点的个数为什么直接就当作1处理了呀?
%%%