建图方式
$1.\;\;$一种最先想到的建图方式是将每个字符串看作图中顶点, 如果字符串$A$与$B$能够相连, 则
从顶点$A$向顶点$B$连一条有向边, 每个顶点的点权即其字符串长度. 这种建图方式对应图的
顶点个数$|V|\le 10^5$, 考虑极端情况: 所有字符串两端的字符均相等, 则图边数$|E|\le 10^{10}$.
$2.\;\;$考虑将一个字符串看为一条从左端两个字符指向右端两个字符的有向边. 即将左右端两个字符
看作图中顶点, 字符串看作一条有向边. 例如$ababc$对应边$V(ab)\rightarrow V(bc)$, 边权即为字符串长度.
这种建图方式对应的边数$|E|\le 10^5$, 顶点个数即两个字母的所有组合数: $|V|\le 26\times 26 = 676$.
通过$2$的建图方式, 原题中每个字符串与图中每个有向边一一对应, 每个单词环也与图中的环一一对应.
$01$分数规划
题目转化为求图环$C$上$\sum w/ \sum 1$的最大值, 参考 AcWing 361. 观光奶牛 关于$01$分数规划的求解过程:
二分环$C$上对应比值的可能最大值, 假设某次二分的值为$mid$, 判断图中是否存在环满足:
$\;\;\;\; \sum w/ \sum 1\gt mid$ <--> $\sum (w - mid\times 1)\gt 0$.
即将原图边权更新, 判断更新后的图中是否存在正环.
具体实现
-
原图无环的判断: 当我们的$mid = 0$时, 边权值实际没有更新, 我们此时判断的是原图中是否存在正环.
由于边权(字符串长度)均为正值, 若此时不存在正环等价于原图不存在环. 所以我们可以用$mid = 0$判断
原图是否有环. -
将字符串两端两个字符哈希为整数值, 可以通过将字符视作$26$进制数值, 将$a\sim z\rightarrow 0\sim 25$.
$O(\lg(1000)nm)\approx 7\times 10^8\; TLE$
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int V = 26 * 26, N = V + 10, M = 1e5 + 10;
int n;
int h[N], e[M], w[M], ne[M], idx;
double dist[N]; int q[N]; bool st[N];
int cnt[N];
void add(int u, int v, int c)
{
e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = 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 < V; i ++ )
{//由于没有输入顶点个数 可以将所有可能顶点全部加入
st[i] = true;
q[tt ++] = i;
}
while( hh != tt )
{
int u = q[hh ++];
if( hh == N ) hh = 0;
st[u] = false;
for( int i = h[u]; ~i; i = ne[i] )
{
int v = e[i];
if( dist[v] < dist[u] + w[i] - mid )
{
dist[v] = dist[u] + w[i] - mid;
cnt[v] = cnt[u] + 1;
if( cnt[v] == V ) return true; //顶点个数 不知多少 取最大可能值
if( !st[v] )
{
st[v] = true;
q[tt ++] = v;
if( tt == N ) tt = 0;
}
}
}
}
return false;
}
int main()
{
char str[1010];
while( scanf("%d", &n), n )
{
memset(h, -1, sizeof h);
idx = 0;
while( n -- )
{
scanf("%s", str);
int len = strlen(str);
if( len >= 2 )
{//边上存在顶点
int u = (str[0] - 'a') * 26 + (str[1] - 'a');
int v = (str[len - 2] - 'a') * 26 + (str[len - 1] - 'a');
add(u, v, len);
}
}
if( !check(0) ) puts("No solution"); //原图无环
else
{
double l = 0, r = 1000;
while( r - l > 1e-4 )
{
double mid = ( l + r ) / 2;
if( check(mid) ) l = mid;
else r = mid;
}
printf("%lf\n", l);
}
}
return 0;
}
优化方式
当$spfa$时间接近$O(nm)$时, 假定图中存在负环. 比较依赖经验以及问题数据, 可能要多尝试不同的数值.
$1.$所有顶点入队次数
一种方式是判断所有顶点入队次数, 一般入队次数大于几倍顶点个数就可以假定图中存在负环.
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int V = 26 * 26, N = V + 10, M = 1e5 + 10;
int n;
int h[N], e[M], w[M], ne[M], idx;
double dist[N]; int q[N]; bool st[N];
int cnt[N];
void add(int u, int v, int c)
{
e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = 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 < V; i ++ )
{//由于没有输入顶点个数 可以将所有可能顶点全部加入
st[i] = true;
q[tt ++] = i;
}
int count = 0; //所有顶点入环次数
while( hh != tt )
{
int u = q[hh ++];
if( hh == N ) hh = 0;
st[u] = false;
for( int i = h[u]; ~i; i = ne[i] )
{
int v = e[i];
if( dist[v] < dist[u] + w[i] - mid )
{
dist[v] = dist[u] + w[i] - mid;
cnt[v] = cnt[u] + 1;
if( cnt[v] == V ) return true; //顶点个数 不知多少 取最大可能值
if( !st[v] )
{
count ++;
if( count > 3 * V ) return true;
st[v] = true;
q[tt ++] = v;
if( tt == N ) tt = 0;
}
}
}
}
return false;
}
int main()
{
char str[1010];
while( scanf("%d", &n), n )
{
memset(h, -1, sizeof h);
idx = 0;
while( n -- )
{
scanf("%s", str);
int len = strlen(str);
if( len >= 2 )
{//边上存在顶点
int u = (str[0] - 'a') * 26 + (str[1] - 'a');
int v = (str[len - 2] - 'a') * 26 + (str[len - 1] - 'a');
add(u, v, len);
}
}
if( !check(0) ) puts("No solution"); //原图无环
else
{
double l = 0, r = 1000;
while( r - l > 1e-4 )
{
double mid = ( l + r ) / 2;
if( check(mid) ) l = mid;
else r = mid;
}
printf("%lf\n", l);
}
}
return 0;
}
$2.spfa$中用栈结构存点
栈相比队列同样可以存储$spfa$中被更新的顶点, 不同的是遍历顺序相反. 这种方式的运行时间不是
很稳定, 但在图中存在负环时运行效率很好. 我的理解是当栈结构第一次遇到负环时, 再第一次经过负环后,
栈会按照环的相反顺序依次将环中顶点出队, 当遇到环的起点时会再次将负环中的顶点入栈, 类似先走一圈
负环, 回退到起点再走一圈.
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int V = 26 * 26, N = V + 10, M = 1e5 + 10;
int n;
int h[N], e[M], w[M], ne[M], idx;
double dist[N]; int q[N]; bool st[N];
int cnt[N];
void add(int u, int v, int c)
{
e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++;
}
bool check(double mid)
{
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
int tt = 0;
for( int i = 0; i < V; i ++ )
{//由于没有输入顶点个数 可以将所有可能顶点全部加入
st[i] = true;
q[tt ++] = i; //此时对应栈
}
int count = 0; //所有顶点入环次数
while( tt )
{
int u = q[-- tt];
//if( hh == N ) hh = 0;
st[u] = false;
for( int i = h[u]; ~i; i = ne[i] )
{
int v = e[i];
if( dist[v] < dist[u] + w[i] - mid )
{
dist[v] = dist[u] + w[i] - mid;
cnt[v] = cnt[u] + 1;
if( cnt[v] == V ) return true; //顶点个数 不知多少 取最大可能值
if( !st[v] )
{
st[v] = true;
q[tt ++] = v;
//if( tt == N ) tt = 0;
}
}
}
}
return false;
}
int main()
{
char str[1010];
while( scanf("%d", &n), n )
{
memset(h, -1, sizeof h);
idx = 0;
while( n -- )
{
scanf("%s", str);
int len = strlen(str);
if( len >= 2 )
{//边上存在顶点
int u = (str[0] - 'a') * 26 + (str[1] - 'a');
int v = (str[len - 2] - 'a') * 26 + (str[len - 1] - 'a');
add(u, v, len);
}
}
if( !check(0) ) puts("No solution"); //原图无环
else
{
double l = 0, r = 1000;
while( r - l > 1e-4 )
{
double mid = ( l + r ) / 2;
if( check(mid) ) l = mid;
else r = mid;
}
printf("%lf\n", l);
}
}
return 0;
}
佬，这里的点的个数为什么直接就当作1处理了呀？