SP2885 WORDRING - Word Rings 题解

题意：

如果字符串 $A$ 的结尾两个字符与字符串 $B$ 的开头两个字符相匹配，我们称 $A$ 与 $B$ 能 “ 相连 ” ( 注意： $A$ 与 $B$ 能相连，不代表 $B$ 与 $A$ 能相连 )

当若干个串首尾 “ 相连 ” 成一个环时，我们称之为一个环串（一个串首尾相连也算）

我们希望从给定的全小写字符串中找出一个环串，使这个环串的平均长度最长
intercommunicational
alkylbenzenesulfonate
tetraiodophenolphthalein
如上例：第一个串能与第二个串相连，第二个串能与第三个串相连，第三个串又能与第一个串相连。按此顺序连接，便形成了一个环串。

长度为 $20+21+24=65$ ( 首尾重复部分需计算两次 ) ，总共使用了 $3$ 个串，所以平均长度是 $65/3\approx 21.6667$

输入格式：

多组数据
每组数据第一行一个整数 $n$ ，表示字符串数量
接下来 $n$ 行每行一个长度小于等于 $1000$ 的字符串
读入以 $n=0$ 结束

输出格式：

若不存在环串，输出 No solution.。否则输出最长的环串平均长度。

~~吐了，一个初值没赋调了半天。~~

注意到每个字符串其实只有开头结尾的几个字符有用

直接把这两个字符组成的串看作结点，不难发现不超过 $26^2 = 676$ 个结点

比如 $\tt{aabbcdcdcab}$ 就是 $\tt{aa}$ 向 $\tt{ab}$ 连一条边，边权为 $11$ 。

看上去是找个最长的环，但是因为是平均值，

所以这道题就变成经典的 $\tt{01}$ 分数规划了，~~虽然稍微有一丢丢不同~~

$\tt{01}$ 分数规划的精髓就在于二分比值，使原本同一事物的两个属性合并。

设环 $C$ 的答案为

$\bar{w} = \dfrac{1}{k}(w_1+w_2+\cdots+w_k)> M$

则不等式等价于

$(M-w_1) + (M-w_2)+\cdots+(M-w_k) < 0$

很好，我们有了新的边权，找负环就好啦！

这个二分边界么，如果有负环，那就 $l \leftarrow \mathrm{mid}$ ，否则 $r \leftarrow \mathrm{mid}$

时间复杂度 $O(-n|\Sigma|\log \epsilon)$

然后这道题愉快地卡了我好久，然后顺便练习了一下卡常

代码1：（bfs版，实测1.78s）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define INF 0x3f3f3f3f
#define N ((int)(888))
#define M ((int)(1e5+15))
const double eps=1e-3;
const int tot=750;
int encode(int a,int b){return (a-'a')*26+b-'a'+1;}
void up(int &x,int y) {x < y ? x = y : 0;}
void down(int &x,int y) {x > y ? x = y : 0;}
bitset<N> vis;
int n,mx,cnt[N];
double d[N]; char s[M];
vector< pair<int,int> > g[N];
void addEdge(int u,int v,int w)
{
	g[u].push_back({v,w});
}
void clear()
{
	mx=0;
	for(int i=1; i<=tot; i++) g[i].clear();
}
bool spfa(double mid)
{
	vis=0; queue<int> q; d[0]=0;
	for(int i=1; i<=tot; i++) cnt[i]=0,d[i]=INF;
	q.push(0); 
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		vis[u]=0;
		for(auto it : g[u])
		{
			int v=it.first; double w=mid-it.second;
			if(d[v] > d[u] + w)
			{
				d[v] = d[u] + w;
				if(!vis[v])
				{
                    if(++cnt[v] > tot) return 1;
					q.push(v); vis[v]=1;
				}
			}
		}
	}
	return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(3);
	while(cin >> n && n)
	{	
		clear();
		for(int i=1,u,v,w; i<=n; i++)
		{
			cin >> s; w=strlen(s);
			if(w<2) continue;
			u=encode(s[0],s[1]); 
			v=encode(s[w-2],s[w-1]);
			addEdge(u,v,w); up(mx, w);
		}
		for(int i=1; i<=tot; i++) addEdge(0,i,0);
		double l,r,mid;
		for(l=0,r=mx; r-l>eps;)
		{
			mid = (l + r) * 0.5;
			spfa(mid) ? l = mid : r = mid;
		}
		l < eps ? (cout << "No solution.\n") : (cout << l << '\n');
	}
    return 0;
}

代码2：（Bellman-Ford，未卡常，实测2.87s）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <bitset>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
// #define INF 0x3f3f3f3f
#define N ((int)(1e3+15))
#define M ((int)(1e5+15))
const double eps=1e-4;
const int tot=777;
int encode(int a,int b){return a * 26 + b - 2619 + 10;}
void up(int &x,int y) {x < y ? x = y : 0;}
void down(int &x,int y) {x > y ? x = y : 0;}

int n,mx,pos=1,head[N];
double d[N]; char s[M];
struct Edge{int u,v,w,next;} e[M];
void addEdge(int u,int v,int w)
{
	e[++pos]={u,v,w,head[u]};
	head[u]=pos;
}
void clear()
{
	mx=0; pos=1;
	memset(head,0,sizeof(head));
}
bool work(double mid)
{
    for(int i=1; i<=tot; i++) d[i]=0;
    for(int k=1; k<=tot; k++)
        for(int i=2; i<=pos; i++)
        {
            int u=e[i].u,v=e[i].v; double w=mid-e[i].w;
            if(d[v] > d[u] + w) d[v]=d[u]+w;
        }
    for(int i=2; i<=pos; i++)
    {
        int u=e[i].u,v=e[i].v; double w=mid-e[i].w;
        if(d[v] > d[u] + w) return 1;
    }
    return 0;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(5);
	while(cin >> n && n)
	{	
		clear();
		for(int i=1,u,v,w; i<=n; i++)
		{
			cin >> s; w=strlen(s);
			if(w<2) continue;
			u=encode(s[0],s[1]); 
			v=encode(s[w-2],s[w-1]);
			addEdge(u,v,w); up(mx, w);
		}
		double l,r,mid;
		for(l=0,r=mx; r-l>eps;)
		{
			mid = (l+r)/2;
			work(mid) ? l = mid : r = mid;
		}
		l < eps ? (cout << "No solution.\n") : (cout << l << '\n');
	}
    return 0;
}