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

把字符串看成圖中的一個頂點，兩字符串匹配則兩個頂點間有邊，從而轉(zhuǎ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;//頂點數(shù)就是字符串的個數(shù)
}MGraph;

void CreateDG(MGraph &G)//構(gòu)造有向圖
{
	int i, j;
	int m;
	cout<<"請輸入要處理的字符串個數(shù)：";
	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] )//改進(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<