UVa 140 - Bandwidth(全排列+回溯剪枝)

给出结点和结点之间的连接,求带宽最小的排列。带宽就是在排列中每一个点到其他点最大距离的最大值。

数据量很小,可以枚举全排列,使用algorithm中的next_permutation函数。

对于每个排列求带宽比较,有一个点的带宽大于当前最小值,就剪掉。

这道题不用函数,手动构造能剪更多枝,可以更加省时,但代码可能会长点。

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
60
61
62
63
64
65
66
67
68
69
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=30;
int a[maxn],b[maxn],n,best,k[10]={1};
bool g[maxn][maxn],vis[maxn];
bool read(){
char c=0,d=0;
best=1<<30,n=0;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(g,0,sizeof(g));
memset(vis,0,sizeof(vis));
while(d!='\n'){
c=getchar();
if(c=='#') return false;
if(!vis[c-'A']) ++n,vis[c-'A']=true;
getchar();
while(isupper(d=getchar())){
if(!vis[d-'A']) ++n,vis[d-'A']=true;
g[c-'A'][d-'A']=true;
g[d-'A'][c-'A']=true;
}
}
return true;
}
int get_bw(){
int bw=0;
for(int i=0;i<n;++i){
if(!vis[a[i]]) continue;
for(int j=0;j<n;++j){
if(!vis[a[j]]) continue;
if(g[a[i]][a[j]])
bw=max(abs(i-j),bw);
if(bw>best) return bw;//有大于当前最小值的就回溯。
}
}
return bw;
}
void solve(){
int sum=k[n];
for(int i=0,j=0;i<n;++i){
while(!vis[j]) ++j;
a[i]=j++;
}
for(int i=0;i<sum;++i){
int t=get_bw();
if(best>t){
for(int j=0;j<n;++j)
b[j]=a[j];
best=t;
}
next_permutation(a,a+n);//枚举全排列。
}
return;
}
int main(){
for(int i=1;i<10;++i) k[i]=i*k[i-1];
while(read()){
solve();
for(int i=0;i<n;++i)
printf("%c ",b[i]+'A');
printf("-> %d\n",best);
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。