Chinaunix首页 | 论坛 | 博客
  • 博客访问: 626278
  • 博文数量: 108
  • 博客积分: 46
  • 博客等级: 民兵
  • 技术积分: 1279
  • 用 户 组: 普通用户
  • 注册时间: 2012-08-16 11:36
个人简介

坐井以观天

文章分类

全部博文(108)

文章存档

2014年(13)

2013年(90)

2012年(6)

分类: C/C++

2013-06-27 17:42:41


题目:
    有n 个长为m+1 的字符串,如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配,则两个字符串可以联接,问这n 个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。

解答:
    把字符串看成图中的一个顶点,两字符串匹配则两个顶点间有边,从而转化为图的问题。
    利用弗洛伊德算法求图的最长路径。
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;

  4. #define INFINITY -10000
  5. #define MAX_VERTEX_NUM 20

  6. typedef struct MGraph{
  7.     string vexs[MAX_VERTEX_NUM];//顶点信息,这里就是要处理的字符串,每个字符串看做一个顶点
  8.     int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵,符合条件的两个字符串之间有边
  9.     int vexnum, arcnum;//顶点数就是字符串的个数
  10. }MGraph;

  11. void CreateDG(MGraph &G)//构造有向图
  12. {
  13.     int i, j;
  14.     int m;
  15.     cout<<"请输入要处理的字符串个数:";
  16.     cin>>G.vexnum;

  17.     cout<<"请输入这"<<G.vexnum<<"个字符串:";
  18.     for(i=0; i<G.vexnum; i++)
  19.         cin>>G.vexs[i];

  20.     cout<<"请输入m:";
  21.     cin>>m;

  22.     for(i=0; i<G.vexnum; i++)
  23.         for(j=0; j<G.vexnum; j++)
  24.         {
  25.             if(G.vexs[i].substr(G.vexs[i].size()-m,m)==G.vexs[j].substr(0,m))//根据前后m个字符是否匹配确定两字符串之间是否有边
  26.                 G.arcs[i][j]=1;
  27.             else
  28.                 G.arcs[i][j]=INFINITY;
  29.         }
  30. }

  31. //利用弗洛伊德算法求各顶点间的最长路径,p保存路径,D保存各顶点间的最长路径,如果出现循环,函数返回false,反之返回true
  32. bool Largeset_FLOYD(MGraph G, int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM], int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM])
  33. {
  34.     int v, w, u;
  35.     int i, j;

  36.     for(v=0; v<G.vexnum; v++)
  37.         for(w=0; w<G.vexnum; w++)
  38.         {
  39.             D[v][w]=G.arcs[v][w];
  40.             for(u=0; u<G.vexnum; u++)
  41.                 p[v][w][u]=-1;
  42.             if(D[v][w]>INFINITY)
  43.             {
  44.                 p[v][w][0]=v;
  45.                 p[v][w][1]=w;
  46.             }
  47.         }

  48.     for(u=0; u<G.vexnum; u++)
  49.         for(v=0; v<G.vexnum; v++)
  50.             for(w=0; w<G.vexnum; w++)
  51.             {
  52.                 if(D[v][u]>INFINITY && D[u][w]>INFINITY && D[v][u]+D[u][w]>D[v][w] )//改进的弗洛伊德算法,求最长路径
  53.                 {
  54.                     D[v][w]=D[v][u]+D[u][w];

  55.                     //更新p,以便打印路径
  56.                     for(i=0; i<G.vexnum; i++)
  57.                     {
  58.                         if(p[v][u][i]!=-1)
  59.                             p[v][w][i]=p[v][u][i];
  60.                         else
  61.                             break;
  62.                     }
  63.                     for(j=1; j<G.vexnum; j++)
  64.                     {
  65.                         if(p[u][w][j]!=-1)
  66.                             p[v][w][i++]=p[u][w][j];
  67.                         else
  68.                             break;
  69.                     }
  70.                     
  71.                 }
  72.             }

  73.     //判断是否有循环
  74.     for(v=0; v<G.vexnum; v++)
  75.         if(D[v][v]!=INFINITY)
  76.                 return false;
  77.     
  78.     return true;
  79. }

  80. void main()
  81. {
  82.     int i, j;
  83.     int posx, posy;
  84.     MGraph g;
  85.     CreateDG(g);

  86.     int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
  87.     int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
  88.     bool flag=true;

  89.     flag=Largeset_FLOYD(g, p, D);

  90. /*    for(i=0; i<g.vexnum; i++)
  91.     {
  92.         for(j=0; j<g.vexnum; j++)
  93.             cout<<D[i][j]<<" ";
  94.         cout<<endl;
  95.     }*/

  96.     
  97.     if(flag)
  98.     {
  99.         cout<<"最大长度为:";
  100.         int max=-10000;
  101.         for(i=0; i<g.vexnum; i++)
  102.             for(j=0; j<g.vexnum; j++)
  103.             {
  104.                 if(D[i][j]>max)
  105.                 {
  106.                     max=D[i][j];
  107.                     posx=i;
  108.                     posy=j;
  109.                 }
  110.             }
  111.         cout<<max<<endl;
  112.         cout<<"字符串链为:";
  113.         for(i=0; i<g.vexnum; i++)//打印字符串链
  114.         {
  115.             if(p[posx][posy][i]!=-1)
  116.                 cout<<g.vexs[p[posx][posy][i]]<<" ";
  117.         }
  118.         cout<<endl;
  119.     }
  120.     else
  121.         cout<<"错误:出现循环"<<endl;

  122. }
    

    参考:http://blog.csdn.net/cxllyg/article/details/7606599

阅读(1219) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~