题意:
给一个图, 将其节点以任一序列排列。
1)计算每个节点距离相邻节点的最大距离 dis[i]
2)计算出当前序列中, 所有节点的dis[i], 并求出最大的dis[i] : max_dis
求最小的max_dis, 并且输出此序列。
节点数不超过8个
思路:
节点数不超过八个, 那直接进行全排列, 求解最小值即可。
复杂度为O(n!)
坑爹的地方在读图, 模拟读图, 得处理好细节, 全排列的生成直接用dfs即可。
代码:
1 #include <cmath>
2 #include <cstdio>
3 #include <cstring>
4 #include <cstdlib>
5 #include <ctime>
6 #include <set>
7 #include <map>
8 #include <list>
9 #include <stack>
10 #include <queue>
11 #include <string>
12 #include <vector>
13 #include <fstream>
14 #include <iterator>
15 #include <iostream>
16 #include <algorithm>
17 using namespace std;
18 #define LL long long
19 #define INF 0x3f3f3f3f
20 #define MOD 1000000007
21 #define eps 1e-6
22 #define MAXN 26
23 #define MAXM 1000
24 #define dd {cout<<"debug"<<endl;}
25 #define pa {system("pause");}
26 #define p(x) {printf("%d\n", x);}
27 #define pd(x) {printf("%.7lf\n", x);}
28 #define k(x) {printf("Case %d: ", ++x);}
29 #define s(x) {scanf("%d", &x);}
30 #define sd(x) {scanf("%lf", &x);}
31 #define mes(x, d) {memset(x, d, sizeof(x));}
32 #define do(i, x) for(i = 0; i < x; i ++)
33 #define dod(i, x, l) for(i = x; i >= l; i --)
34 #define doe(i, x) for(i = 1; i <= x; i ++)
35 int len, max_ans, n;
36 char str[MAXM];
37 vector <int> V[MAXN];
38 int ans[MAXN];
39 int order[MAXN];
40 bool vis[MAXN];
41 void init()
42 {
43 memset(ans, 0, sizeof(ans));
44 memset(vis, false, sizeof(vis));
45 memset(order, 0, sizeof(order));
46 for (int i = 0; i < MAXN; i ++)
47 V[i].clear();
48 max_ans = INF;
49 n = 0;
50 }
51 void read()
52 {
53 len = strlen(str);
54 bool flag = false;
55 char ch;
56 for (int pos = 0; pos < len; pos ++)
57 {
58 if (str[pos] >= 'A' && str[pos] <= 'Z')
59 {
60 if (!vis[str[pos] - 'A'])
61 {
62 vis[str[pos] - 'A'] = true;
63 n ++;
64 }
65 if (!flag)
66 {
67 ch = str[pos];
68 flag = true;
69 }
70 else
71 {
72 if (find(V[ch - 'A'].begin(), V[ch - 'A'].end(), str[pos] - 'A') == V[ch - 'A'].end())
73 V[ch - 'A'].push_back(str[pos] - 'A');
74 if (find(V[str[pos] - 'A'].begin(), V[str[pos] - 'A'].end(), ch - 'A') == V[str[pos] - 'A'].end())
75 V[str[pos] - 'A'].push_back(ch - 'A');
76 }
77 }
78 else if (str[pos] == ';')
79 {
80 flag = false;
81 }
82 else if (str[pos] == ':')
83 continue;
84 }
85 memset(vis, false, sizeof(vis));
86 }
87 void show()
88 {
89 printf("%d\n", n);
90 for (int i = 0; i < MAXN; i ++)
91 if (!V[i].empty())
92 {
93 printf("%c:", i + 'A');
94 for (int j = 0; j < V[i].size(); j ++)
95 printf(" %c", V[i][j] + 'A');
96 printf("\n");
97 }
98 }
99 int get_ans()
100 {
101 int max_num = 0;
102 int temp = 0;
103 for (int i = 0; i < MAXN; i ++)
104 {
105 temp = 0;
106 if (ans[i] == 0) continue;
107 for (int j = 0; j < V[i].size(); j ++)
108 {
109 int x = abs(ans[V[i][j]] - ans[i]);
110 if (x > temp)
111 temp = x;
112 }
113 max_num = max(max_num, temp);
114 }
115 return max_num;
116 }
117 void dfs(int root, int num)
118 {
119 ans[root] = num;
120 if (num == n)
121 {
122 int x = get_ans();
123 if (x < max_ans)
124 {
125 max_ans = x;
126 for (int i = 0; i < MAXN; i ++)
127 if (ans[i])
128 order[ans[i]] = i;
129 }
130 return ;
131 }
132
133 for (int u = 0; u < MAXN; u ++)
134 if (!vis[u] && !V[u].empty())
135 {
136 vis[u] = true;
137 dfs(u, num + 1);
138 vis[u] = false;
139 }
140 }
141 void solve()
142 {
143 init();
144 read();
145 for (int i = 0; i < MAXN; i ++)
146 if (!V[i].empty())
147 {
148 memset(vis, false, sizeof(vis));
149 memset(ans, 0, sizeof(ans));
150 vis[i] = true;
151 dfs(i, 1);
152 }
153 for (int i = 1; i <= n; i ++)
154 printf("%c ", order[i] + 'A');
155 printf("-> %d\n", max_ans);
156 }
157
158 int main()
159 {
160 while (gets(str))
161 {
162 if (!strcmp(str, "#")) break;
163 solve();
164 }
165 return 0;
166 }