1699.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#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;
}