题意:任意一个点都至少有一个点与其相连接,所有的点可以进行任意排列,总排列数为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] == ' ')
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, ' ', sizeof(edge));
memset(v, ' ', 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;
}