bandwidth(dfs剪枝).cpp

杭电acm解题报告2001---2099.

//uva 140
//lrj 180
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

bool path[30][30];
bool have[30];
int pos[30];
int mmin, hs;
char ans[30], str[30];

void make_graph(char * line)
{
	int i,j,len = strlen(line);
	memset(path,0,sizeof(path));
	memset(have,0,sizeof(have));
	hs = 0;

	for(i=0;i<len;i++) {
		char s = line[i];
		if(!have[s-'A']) {
			hs ++;
			have[s-'A'] = true;
		}
		i += 2;
		while(i < len && line[i] != ';') {
			char t = line[i];
			if(!have[t-'A']) {
				hs ++;
				have[t-'A'] = true;
			}
			path[s-'A'][t-'A'] = path[t-'A'][s-'A'] = true;
			i ++;
		}
	}
}

void
dfs(int deep, int k)
{
	int i,j,t;
	bool flag;
	if(deep == hs && mmin > k) {
		mmin = min(mmin, k);
		str[deep] = 0;
		strcpy(ans,str);
		return;
	}
	for(i='A'-'A';i<='Z'-'A';i++) {
		if(have[i] && pos[i] == -1) {//find un-visited point
			flag = true;
			t = 0;
			for(j='A'-'A';j<='Z'-'A';j++) {
				if(path[j][i]) {
					if(pos[j] != -1) {
						k = max(k, deep - pos[j]);//max distance
					}
					else {
						t ++;//non-visited
					}
				}
			}//find and cal
			if(k >= mmin || t >= mmin) {//two pruning
				continue;
			}
			pos[i] = deep;
			str[deep] = i+'A';
			dfs(deep+1, k);
			pos[i] = -1;
		}
	}
}

int
main()
{
	int i,j;
	char line[1100];
	while(gets(line)) {
		if(line[0] == '#') {
			break;
		}
		make_graph(line);
		memset(pos,-1,sizeof(pos));
		mmin = INT_MAX;
		dfs(0, 0);
		for(i=0; ans[i] ;i++) {
			printf("%c ", ans[i]);
		}
		printf("-> %d\n", mmin);
	}
}