uva140-暴力枚举

题意:任意一个点都至少有一个点与其相连接,所有的点可以进行任意排列,总排列数为n!.

一个点带宽定义与它相连的点的最远距离,一个排列的带宽定义为,点中最大的带宽,找出带宽最小的那个排列,有多组,输出字典序最小

#include<stdio.h>

#include<iostream>

#include<sstream>

#include<queue>

#include<map>

#include<memory.h>

#include <math.h>

#include<time.h>

#include <stdlib.h>

using namespace std;

char v[8];

char edge[100][100];

int tv = 0;

char res[8];

int maxl = 0x7fffffff;

int com(char r[])

{

	int max = -1;

	for(int i = 0; i < tv; i++)

	{

		char c = r[i];

		for(int j = 0; j < 100; j++)

		{

			if(edge[c][j] == '\0')

				break;

			char cc = edge[c][j];

			int k = 0;

			for(k = 0; k < tv; k++)

			{

				if(r[k] == cc)

					break;

			}

			int l = k - i;

			l = l < 0 ? l * -1 : l;

			max = max < l ? l : max;

		}

	}

	if(max < maxl)

	{

		maxl = max;

		memcpy(res, r, sizeof(char) * tv);

	}

	return 0;

}

void dfs(int cur, int vis[], char r[])

{

	if(cur == tv)

	{

		com(r);

		return;

	}

	for(int i = 0; i < tv; i++)

	{

		if(vis[i] == 1)

			continue;

		vis[i] = 1;

		r[cur] = v[i];

		cur++;

		dfs(cur, vis, r);

		cur--;

		vis[i] = 0;

	}

}

void sort()

{

	for(int i = 0; i < tv; i++)

	{

		for(int j = 1; j < tv - i; j++)

		{

			if(v[j - 1] > v[j])

			{

				char t = v[j - 1];

				v[j - 1] = v[j];

				v[j] = t;

			}

		}

	}

}

int main()

{

	//freopen("d:\\1.txt", "r", stdin);

	while (cin)

	{

		string str;

		cin >> str;

		if(str == "#")

			break;

		istringstream is(str);

		memset(edge, '\0', sizeof(edge));

		memset(v, '\0', sizeof(v));

		tv = 0;

		maxl = 0x7fffffff;

		int index[100];

		int mark[100][100];

		int mark2[100];

		memset(index, 0, sizeof(index));

		memset(mark, 0, sizeof(mark));

		memset(mark2, 0, sizeof(mark2));

		char c;

		char cc;

		while (is >> c)

		{

			if(c == ':')

			{

				continue;

			}

			if(c == ';')

			{

				is >> cc;

				if(mark2[cc] == 0)

				{

					v[tv++] = cc;

					mark2[cc] = 1;

				}

				continue;

			}

			if(tv == 0)

			{

				cc = c;

				mark2[cc] = 1;

				v[tv++] = cc;

				continue;

			}

			if(mark[cc][c] != 1)

			{

				edge[cc][index[cc]++] = c;

				mark[cc][c] = 1;

			}

			if(mark[c][cc] != 1)

			{

				edge[c][index[c]++] = cc;

				mark[c][cc] = 1;

			}

			if(mark2[c] == 0)

			{

				mark2[c] = 1;

				v[tv++] = c;

			}

		}

		//枚举

		int vis[10];

		memset(vis, 0, sizeof(vis));

		char r[8];

		sort();

		dfs(0, vis, r);

		for(int i = 0; i < tv; i++)

			cout << res[i] << " ";

		cout << "-> " << maxl << endl;

	}

	return 0;

}