UVa 140 - Bandwidth（全排列＋回溯剪枝）

发表于 分类于 ， Disqus：

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

数据量很小，可以枚举全排列，使用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博客，格式可能有所偏差。 **

相关文章