生成全排列，然后从中选择最优解即可。
输入输出被我弄得有点麻烦了……
以下是我的代码：
#include<iostream>
#include<string>
#include<algorithm>
#include<cctype>
using namespace std;
const int kMaxn(10);
const int kInf(930315);
int n,ans,r[kMaxn],v[kMaxn];
bool map[kMaxn][kMaxn],used[kMaxn];
void dfs(int depth)
{
if(depth>n)
{
int now(0);
for(int i=1;i<=n;i++)
for(int j=n;j>i;j--)
if(map[r[i]][r[j]])
{
now=max(now,j-i);
break;
}
if(ans>now)
{
ans=now;
for(int i=1;i<=n;i++)
v[i]=r[i];
}
return;
}
for(int i=1;i<=n;i++)
if(!used[i])
{
r[depth]=i;
used[i]=true;
dfs(depth+1);
r[depth]=0;
used[i]=false;
}
}
int main()
{
string graph;
while(cin>>graph && graph!="#")
{
bool t[27]={false};
for(int i=0;i<graph.size();i++)
if(isalpha(graph[i]))
t[graph[i]-'A']=true;
n=0;
for(int i=0;i<26;i++)
if(t[i])
n++;
for(int i=0;i<graph.size();i++)
if(isalpha(graph[i]))
{
int cnt(0);
for(int j=0;j<=graph[i]-'A';j++)
if(t[j])
cnt++;
graph[i]=cnt+'0';
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=false;
for(int i=0;i<graph.size();i++)
{
int k(graph[i]-'0');
i+=2;
while(i<graph.size() && graph[i]!=';')
{
map[k][graph[i]-'0']=true;
map[graph[i]-'0'][k]=true;
i++;
}
}
ans=kInf;
fill(used,used+kMaxn,false);
dfs(1);
for(int i=1;i<=n;i++)
{
int j,cnt(0);
for(j=0;j<26;j++)
if(t[j])
{
cnt++;
if(cnt>=v[i])
break;
}
cout<<(char)(j+'A')<<" ";
}
cout<<"-> "<<ans<<endl;
}
return 0;
}
posted on 2011-04-19 21:00
lee1r 阅读(232)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索