WORDRING - Word Rings

2021-05-15 21:04:42


算法:SPFA


题目大意:

基本是要把单词都串成一个环,输出一个平均长度最长的环(注意 平 均长度是把所有的环加起来除个数)。


思路分析:

刚看开题会的觉得没什么思路,仔细一看其实可以把两边的字符看 成点,长度看成边,这么一连转化成了一道图论题,求平均最长的 环,我们可以用BFS优化的的SPFA来求最短路的问题,这里我是 用的是 DFS优化的SPFA。

具体分析:

我们如何来保存这个点呢??


点:把字符当成26进制,这样就可以得到1000以内的点。


边:边处理更简单了,长度即使边长。

  void add1(ll x,ll y,long double w)
  {
      nex[++tot]=fir[x];fir[x]=tot;go[tot]=y;ww[tot]=w;
  }

这是图论中基本存边的方式。


接下来就是重要的部分了;我们没有什么好的方法来求平均最长的方 法,但我们可以用dfs很好的判断是否有环。

我们用l1来表示第一条边,l2第二条等等。

平均数=(l1+l2+l3+...+lN)/N。

即 (l1-平均数)+(l2-平均数)+(l3-平均数)+...+(lN-平均数) =0。

我们可以直接在1000内用二分查找的办法找在每条边减去当前平均值 情况下是否存在一个正环,如果有则l=mid,否则r=mid。


  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函数主要就是确定在当前平均值的情况下,存在不存在大于等 于此平均值的正环。

  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;
  }

这道题就差不多完成了,下面直接上代码。


代码部分:

  #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;
  }