-
Notifications
You must be signed in to change notification settings - Fork 2
/
带宽(2).cpp
59 lines (52 loc) · 1.22 KB
/
带宽(2).cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 10;
int id[256], letter[maxn];
int main(){
char input[1000];
while(scanf("%s", input)==1 && input[0]!='#'){
// 计算节点个数并给字母编号
int n = 0;
for(char ch='A'; ch<='Z'; ch++){
if(strchr(input, ch)){
id[ch] = n++;
letter[id[ch]] = ch;
}
}
// 处理输入
int len = strlen(input), p = 0, q = 0;
vector<int> u,v;
while(1){
while(p<len && input[p]!=':') p++;
if(p == len) break;
while(q<len && input[q]!=';') q++;
for(int i = p+1; i < q; i++){
u.push_back(id[input[p-1]]);
v.push_back(id[input[i]]);
}
p++;
q++;
}
// 枚举全排列
int P[maxn], bestP[maxn], pos[maxn], ans = n;
for(int i = 0; i < n; i++) P[i] = i;
do{
for(int i = 0; i < n ;i++) pos[ P[i] ] = i; // 每个字母的位置
int bandwidth = 0;
for(int i = 0; i < u.size(); i++){
bandwidth = max(bandwidth, abs( pos[u[i]] - pos[v[i]] )); // 计算带宽
}
if(bandwidth < ans){
ans = bandwidth;
memcpy(bestP, P, sizeof(int)*n);
}
}while(next_permutation(P, P+n));
// 输出
for(int i = 0; i < n;i++) printf("%c ", letter[ bestP[i] ]) ;
printf("-> %d\n", ans);
}
return 0;
}