问题描述：
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们己知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙" 中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入:
输入的第一行为一个单独的整数n(n<=20）表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表来“龙”开头的字母。你可以假定以此字母开头的“龙"一定存在
输出:
只需输出以此字母开头的最长的“龙”的长度
样例输入:
5
at
touch
cheat
choose
tact
a
输出
23 (连成的“龙”为atoucheatactactouchoose)
分析：
建立一个无向图，用来保存各个单词之间连接的最大增加长度，glen[i][j]表示i与j连成一个龙是可以增加的最大长度，再进行回溯求出最大长度即可。
优化：其实是题目中有的，每个单词最多用2次。
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
char s[30][300],head;
int glen[30][30],used[30];
int n,ans;
void make_g()
{
memset(glen,0,sizeof(glen));
int Min,pos,bk;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
if (strlen(s[i])<strlen(s[j])) Min=strlen(s[i]);
else Min=strlen(s[j]);
for (int k=1;k<=Min-1;k++)
{
bk=1;
for (int t=1;t<=k;t++)
if (s[j][t-1]!=s[i][strlen(s[i])-k+t-1])
{
bk=0; break;
}
if (bk)
{
pos=k; break;
}
}
if (bk) glen[i][j]=strlen(s[j])-pos;
else glen[i][j]=0;
}
}
void Search(int last,int len)
{
if (len>ans) ans=len;
for (int j=1;j<=n;j++)
if (glen[last][j] && used[j]<2)
{
used[j]++;
Search(j,len+glen[last][j]);
used[j]--;
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%s",s[i]);
getchar();
scanf("%c",&head);
make_g();
ans=0;
memset(used,0,sizeof(used));
for (int i=1;i<=n;i++)
if (s[i][0]==head)
{
used[i]=1;
Search(i,strlen(s[i]));
used[i]=0;
}
printf("%d\n",ans);
return 0;
}