Bandwidth UVA - 140(dfs)

题目大意：
给你一个图有n个节点m条边，输入的形式：A:FB;表示从节点A到F和B各有一条边，你可以任意改变字节点的位置，然后求他的最大距离，有n！种组合，问你所有最大值的组合中最小值是多少？输出并且打印。
思路：
先用图建边，然后dfs求排列找最大距离，然后找所有最大距离的最小值。
我对深度建立了一个索引，还有一个麻烦的地方，输入的可能是随机字母而不是连续的，所以还需要一个数组存字母，判断的时候也需要注意一下，总的来书思路不难代码比较难写。。。。。。。调了两个多小时终于a了（哭）
代码：

#include<bits/stdc++.h>
using namespace std;

bool a[100][100];
int cnt=0;
int vis[1000];
int path[1000];
int minn,maxn;
int ans[100];
int index1[100];
int sava[100];
char tt[100]={'J', 'L', 'Q', 'V', 'C', 'X', 'Z', 'T'};
void DFS(int dep){
	if(dep==cnt){
		int maxn=-999999;
		for(int i=0;i<cnt;i++){
			index1[path[i]]=i;
		}
		/*bool flag=0; for(int i=0;i<cnt;i++){ if((path[i]+'A')!=tt[i])flag=1; } if(!flag){ cout<<a['Q'-'A']['X'-'A']<<endl; cout<<index1['Q'-'A']<<" "<<index1['X'-'A']<<endl; for(int i=0;i<cnt;i++){ cout<<index1[path[i]]<<" : "<<(char)(path[i]+'A')<<endl; } }*/
		for(int i=0;i<dep;i++){
			for(int j=0;j<cnt;j++){
				if(a[path[i]][sava[j]]){
					if(abs(index1[path[i]]-index1[sava[j]])>maxn){
						maxn=abs(index1[path[i]]-index1[sava[j]]);
					}
				}
			}
		}
		if(maxn<minn){
			minn=maxn;
			for(int i=0;i<cnt;i++)ans[i]=path[i];
		} 
		return ;
	}
	for(int i=0;i<cnt;i++){
		if(!vis[i]){
			vis[i]=1;
			path[dep]=sava[i];
			DFS(dep+1);
			vis[i]=0;
		}
	}
}
int main(){
	string str;
	while(cin>>str&&str[0]!='#'){
		memset(path,0,sizeof(path));
		memset(vis,0,sizeof(vis));
		memset(a,0,sizeof(a));
		cnt=0;
		minn=0x3f3f3f3f;
		char tem;
		bool flag=0;
		for(int i=0;i<str.size();i++){
			if(str[i]==':'){
				flag=1;
			}else if(str[i]==';'){
				flag=0;
			}else{
				if(path[str[i]-'A']==0){
					sava[cnt]=str[i]-'A';
					cnt++;path[str[i]-'A']=1;
				}
				if(flag){
					a[tem-'A'][str[i]-'A']=1;
					a[str[i]-'A'][tem-'A']=1;
				}else{
					tem=str[i];
				}
			}
		}
		sort(sava,sava+cnt);
		memset(path,0,sizeof(path));
		DFS(0);
		for(int i=0;i<cnt;i++){
			printf("%c ",ans[i]+'A');
		}
		if(minn==-999999){
			cout<<"-> "<<1<<endl;
		}else
		cout<<"-> "<<minn<<endl;
	}
}