这题只要想到是最优完备匹配就行了；

题意：给出n个字符串，若两两相连，将前一个反置添加到后一个后面，相连的值为两个字串从头开始相等的字符个数；

问如何匹配得出最大值；

思路：建图，套模板。

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define CLR(arr, what) memset(arr, what, sizeof(arr))

#define maxn  305

#define INF  (1<<30)-1

int g[maxn][maxn];

int lx[maxn],ly[maxn],match[maxn];

bool visx[maxn],visy[maxn];

int slack[maxn];

int n,m;

char str[maxn][10001];

bool dfs(int cur){

     visx[cur] = true;

     for(int y=1;y<=m;y++){

         if(visy[y])   continue;

         int t=lx[cur]+ly[y]-g[cur][y];

         if(t==0){

            visy[y] = true;

            if(match[y]==-1||dfs(match[y])){

                match[y] = cur;

                return true;

            }

         }

         else if(slack[y]>t){

                 slack[y]=t;

         }

     }

     return false;

}

int KM(){

    CLR(match,-1);

    CLR(ly,0);;

    for(int i=1 ;i<=n;i++){

         lx[i]=-INF;

       for(int j=1;j<=m;j++)

           if(g[i][j]>lx[i])   lx[i]=g[i][j];

   }

   for(int x=1;x<=n;x++){

        for(int i=1;i<=m;i++)  slack[i]=INF;

        while(true){

            CLR(visx,false);

            CLR(visy,false);

            if(dfs(x))  break;

            int d=INF;

            for(int i=1;i<=m;i++){

               if(!visy[i]&&d>slack[i])     d=slack[i];

            }

            for(int i=1;i<=n;i++){

               if(visx[i])                  lx[i]-=d;

            }

            for(int i=1;i<=m;i++){

               if(visy[i])                 ly[i]+=d;

               else                        slack[i]-=d;

            }

        }

   }

    int result = 0;

    for(int i = 1; i <=m; i++)

    if(match[i]!=-1)

        result += g[match[i]][i];

    return result;

}

int solve(int i,int j)

{

	if(i==j) return 0;

	int len1=strlen(str[i]);

	int len2=strlen(str[j]);

	int P = len1-1;

	int Q = 0;

	while(P >= 0 && Q < len2 && str[i][P] == str[j][Q])

	{

			P--;

			Q++;

	}

	return Q;

}

int main(){

    while(scanf("%d",&n)!=EOF){

        CLR(g,0);

        m=n;

        for(int i=1;i<=n;i++)

        {

        	scanf("%s",str[i]);

        }

        for(int i=1;i<=n;i++)

		{

			for(int j=1;j<=n;j++)

			{

				int k=solve(i,j);

				g[i][j]=k;

			}

		}

        printf("%d\n",KM());

    }

    return 0;

}