WORDRING - Word Rings
EBeason
2021-05-15 21:04:42
# **算法：SPFA**
------------
### **题目大意：**
基本是要把单词都串成一个环，输出一个平均长度最长的环
（注意：平均长度是把所有的环加起来除个数）。
------------
### **思路分析：**
刚看始开题会的觉得没什么思路，仔细一看其实可以把两边的字符看成点，长度看成边，这么一连转化成了一道图论题，求平均最长的 环,我们可以用 ~~BFS 优化的的 SPFA~~ 来求最短路的问题，这里我用的是 DFS 优化的 SPFA 。
### **具体分析：**
我们如何来保存这个点呢？？
------------
点：把字符当成$26$进制，这样就可以得到$1000$以内的点。
------------
边：边处理更简单了，长度即使边长。
```cpp
void add1(ll x,ll y,long double w)
{
nex[++tot]=fir[x];fir[x]=tot;go[tot]=y;ww[tot]=w;
}
```
这是图论中基本存边的方式。
------------
接下来就是重要的部分了；我们没有什么好的方法来求平均最长的方法，但我们可以用 dfs 很好的判断是否有环。
我们用 $l_1$ 来表示第一条边，$l_2$ 第二条等等。
平均数 $\bar{l}=\Large\Large\frac{l_1+l_2+l_3+...+l_N}{N}$。
即
$(l_1-\bar{l})+(l_2-\bar{l})+(l_3-\bar{l})+...+(l_N-\bar{l})=\large\sum_{i=1}^{N}(l_i-\bar{l})=0$
我们可以直接在1000内用二分查找的办法找在每条边减去当前平均值 情况下是否存在一个正环，如果有则 ```l=mid``` ，否则 ```r=mid``` 。
------------
```cpp
long double l=1,r=1000,best=-1,mid，jd=0.001;
while(l+jd<r)//0.001用来精度处理，避免程序死循环。
{
mid=(l+r)/2;
if(sovle(mid))
{
best=mid;
l=mid;
}
else
r=mid;
}
if(best==-1) printf("No solution.\n");
else printf("%.2Lf\n",best);
```
```jd``` 可以巧妙地解决精度问题。
------------
### **SPFA部分：**
```solve``` 函数主要就是确定在当前平均值的情况下，存在不存在大于等于此平均值的正环。
```cpp
void spfa(ll x,ll fa,long double w)
{
if(PC) return;//如果有环就返回
pd[x]=fa;
for(int i=fir[x];i;i=nex[i])//循环找边
{
ll v=go[i];
if(d[x]+ww[i]-w>d[v])// 注意这个w一定要全部减去目前 这个平均值
{
d[v]=d[x]+ww[i]-w;
if(d[v]>maxedge){PC=1;return;}//边已经超过所有 边的和，有环。
if(!pd[v])
spfa(v,fa,w);
if(PC) return;
else if(pd[v]==fa)//如果已经第二次来这个地方返 回
{
PC=1;
return;
}
}
}
pd[x]=0;//回溯
}
bool sovle(long double x)
{
PC=0;
memset(d,0,sizeof(d));
memset(pd,0,sizeof(pd));
for(int i=1;i<=702;i++)//不是从每个点都可以找到一个正环，要从每个点试一试。
{
spfa(i,i,x);
if(PC)
break;
}
return PC;
}
```
这道题就差不多完成了，下面直接上代码。
------------
### **代码部分：**
```cpp
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
#define ll long long
const int MaxM=1e5+100;
const int MaxN=1e3+10;
const long double inf=1e9+10;
const long double jd=0.001;
ll N,maxedge,top,PC,pd[MaxN],yw[MaxN];
ll fir[MaxM],nex[MaxM],go[MaxM],tot;
long double ww[MaxM],d[MaxN];
void add1(ll x,ll y,long double w)
{
nex[++tot]=fir[x];fir[x]=tot;go[tot]=y;ww[tot]=w;//添加边的基本模板
}
void spfa(ll x,ll fa,long double w)
{
if(PC) return;
pd[x]=fa;
for(int i=fir[x];i;i=nex[i])
{
ll v=go[i];
if(d[x]+ww[i]-w>d[v])
{
d[v]=d[x]+ww[i]-w;
if(d[v]>maxedge){PC=1;return;}//边已经超过所有边的和，有环。
if(!pd[v])
spfa(v,fa,w);
if(PC) return;
else if(pd[v]==fa)//如果已经第二次来这个地方返回
{
PC=1;
return;
}
}
}
pd[x]=0;
}
bool sovle(long double x)
{
PC=0;
memset(d,0,sizeof(d));
memset(pd,0,sizeof(pd));
for(int i=1;i<=702;i++)//从所有点开始搜索
{
spfa(i,i,x);
if(PC)
break;
}
return PC;
}
int main()
{
while(scanf("%lld",&N)&&N)
{
maxedge=0;
memset(fir,0,sizeof(fir));tot=0;top=0;
for(int i=1;i<=N;i++)//处理边和点
{
string ss;
cin>>ss;
ll len=ss.size();
maxedge=max(maxedge,len);
ll x=(ss[0]-'a'+1)*26+ss[1]-'a'+1;//26进制保存点
ll y=(ss[len-2]-'a'+1)*26+ss[len-1]-'a'+1;
## yw[x]=1;yw[y]=1;
long double lg=len;//把边开成实数型的
add1(x,y,lg);
}
maxedge*=N;//所有边和的最大值
long double l=1,r=1000,best=-1,mid;
while(l+jd<r)
{
mid=(l+r)/2;
if(sovle(mid))
{
best=mid;
l=mid;
}
else r=mid;
}
if(best==-1) printf("No solution.\n");
else printf("%.2Lf\n",best);
}
return 0;
}
```