有n 個(gè)長為m+1 的字符串，求前后m個(gè)字符匹配所能形成的最長字符串鏈：利用弗洛伊德算法求最長路徑

有n 個(gè)長為m+1 的字符串，如果某個(gè)字符串的最后m 個(gè)字符與某個(gè)字符串的前m 個(gè)字符匹配，則兩個(gè)字符串可以聯(lián)接，問這n 個(gè)字符串最多可以連成一個(gè)多長的字符串，如果出現(xiàn)循環(huán)，則返回錯(cuò)誤。

把字符串看成圖中的一個(gè)頂點(diǎn)，兩字符串匹配則兩個(gè)頂點(diǎn)間有邊，從而轉(zhuǎn)化為圖的問題。

利用弗洛伊德算法求圖的最長路徑。

#include 
#include 
using namespace std;

#define INFINITY -10000  
#define MAX_VERTEX_NUM 20 

typedef struct MGraph{
	string vexs[MAX_VERTEX_NUM];//頂點(diǎn)信息，這里就是要處理的字符串，每個(gè)字符串看做一個(gè)頂點(diǎn)
	int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣，符合條件的兩個(gè)字符串之間有邊
	int vexnum, arcnum;//頂點(diǎn)數(shù)就是字符串的個(gè)數(shù)
}MGraph;

void CreateDG(MGraph &G)//構(gòu)造有向圖
{
	int i, j;
	int m;
	cout<<"請(qǐng)輸入要處理的字符串個(gè)數(shù)：";
	cin>>G.vexnum;

	cout<<"請(qǐng)輸入這"<>G.vexs[i];

	cout<<"請(qǐng)輸入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] )//改進(jìn)的弗洛伊德算法，求最長路徑
				{
					D[v][w]=D[v][u]+D[u][w];

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