有n 个长为m+1 的字符串，求前后m个字符匹配所能形成的最长字符串链：利用弗洛伊德算法求最长路径

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

把字符串看成图中的一个顶点，两字符串匹配则两个顶点间有边，从而转化为图的问题。

利用弗洛伊德算法求图的最长路径。

#include 
#include 
using namespace std;

#define INFINITY -10000  
#define MAX_VERTEX_NUM 20 

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

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

	cout<<"请输入这"<>G.vexs[i];

	cout<<"请输入m：";
	cin>>m;

	for(i=0; iINFINITY)
			{
				p[v][w][0]=v;
				p[v][w][1]=w;
			}
		}

	for(u=0; uINFINITY && D[u][w]>INFINITY && D[v][u]+D[u][w]>D[v][w] )//改进的弗洛伊德算法，求最长路径
				{
					D[v][w]=D[v][u]+D[u][w];

					//更新p，以便打印路径
					for(i=0; imax)
				{
					max=D[i][j];
					posx=i;
					posy=j;
				}
			}
    	cout<