[cpp]
描述：好坑人的題，主要是這道題存在這樣的數據A:B;B:CE;CG:D;D:E;E:F;F:G;G:H;H:A，結果好幾次wa……
#include <cstdio>
#include <cstring>
#include <cctype>
int count,len,sum,max;
int score[27],flag[27],out[27],num[27][27];
char s[200];
void bandwidth()
{
int c(0);
for(int i=0; i<count; i++)
for(int k=i+1; k<count; k++)
if(num[score[i]][score[k]])
{
if(c<k-i) c=k-i;
if(c>=sum) return;
}
for(int i=0; i<count; i++) out[i]=score[i];
sum=c;
}
void dfs(int l)
{
if(l>=count)
{
bandwidth();
return;
}
for(int i=0; i<=max; i++)
if(flag[i])
{
flag[i]=0;
score[l]=i;
dfs(l+1);
flag[i]=1;
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("a.txt","r",stdin);
#endif
while(gets(s))
{
if(s[0]=='#') break;
memset(num,0,sizeof(num));
memset(flag,0,sizeof(flag));
count=max=0;
sum=27;
len=strlen(s);
int temp=len;
for(int i=0; i<len; i++)
if(isalpha(s[i]))
{
flag[s[i]-'A']=1;
int k=i+1,j;
for(; k<len; k++) if(s[k]==':') break;
for( j=k+1; j<len; j++)
if(isalpha(s[j])) num[s[i]-'A'][s[j]-'A']=num[s[j]-'A'][s[i]-'A']=flag[s[j]-'A']=1;
else if(s[j]==';')
{
temp=j;
break;
}
if(j==len) temp=len;
}
else if(s[i]==':') i=temp;
for(int i=0; i<26; i++)
if(flag[i])
{
count++;
max=i;
}
for(int i=0; i<=max; i++)
if(flag[i])
{
flag[i]=0;
score[0]=i;
dfs(1);
flag[i]=1;
}
for(int i=0; i<count; i++)
printf("%c ",'A'+out[i]);
printf("-> %d\n",sum);
}
return 0;
}
