http://poj.org/problem?id=1699
#include<iostream>
#include"string.h"
#include<vector>
#include<algorithm>
using namespace std;
int m[10][10];
int set[10];
int len[10];int n;
int order1[10][9],order2[10][9];
char word[10][22];
int h;
int cmp1(int a,int b)
{return m[h][a]>m[h][b];}
int cmp2(int a,int b)
{return m[a][h]>m[b][h];}
int link(int a,int b)
{int i,j;
for(i=0;i<=len[a];i++)
for(j=0;j<=len[b];j++)
{if(i+j>=len[a]||j==len[b])return j;
if(word[a][i+j]!=word[b][j])break;
}
return 0;
}
int best;
void find(int lennow,int head,int tail,int l)
{int i;
if(lennow>=best)return;
if(l==n&&best>lennow)
{best=lennow;return;}
for(i=0;i<n-1;i++)
{if(!set[order2[head][i]]){set[order2[head][i]]=1;
find(lennow+len[order2[head][i]]-m[order2[head][i]][head],order2[head][i],tail,l+1);
set[order2[head][i]]=0;
}
if(!set[order1[tail][i]]){set[order1[tail][i]]=1;
find(lennow+len[order1[tail][i]]-m[tail][order1[tail][i]],head,order1[tail][i],l+1);
set[order1[tail][i]]=0;
}
}
}
int main()
{int i,t,j,k,num;
cin>>t;
while(t--)
{cin>>n;
for(i=0;i<n;i++){cin>>word[i];len[i]=strlen(word[i]);set[i]=0;}
for(i=0;i<n;i++)
{k=0;
for(j=0;j<n;j++)
if(i!=j){m[i][j]=link(i,j);
m[j][i]=link(j,i);
order1[i][k]=j;
order2[i][k++]=j;
if(!set[j]&&(m[i][j]==len[i]||m[j][i]==len[i]))set[i]=1;
if(!set[i]&&(m[i][j]==len[j]||m[j][i]==len[j]))set[j]=1;
}
}
num=0;h=-1;
for(i=0;i<n;i++)if(set[i])num++;
else {h=i;sort(&order1[i][0],&order1[i][n-1],cmp1);
sort(&order2[i][0],&order2[i][n-1],cmp2);
}
best=9999;
if(h==-1){for(i=0;i<n;i++)if(best>len[i])best=len[i];}
else {set[h]=1;find(len[h],h,h,num+1);}
cout<<best<<endl;
}
return 0;
}