UVA-140 Bandwidth 带宽

110 阅读 0 评论 73 点赞

我是靠谱客的博主淡淡绿草，这篇文章主要介绍UVA-140 Bandwidth 带宽，现在分享给大家，希望可以做个参考。

题目链接：https://vjudge.net/problem/UVA-140

题意：给出一个n（n<=8）个结点的图G和一个结点的排列，定义结点 i 的宽带b(i)为 i 和相邻结点在排列中的最远距离，而所有b(i)的最大值就是整个图的G，一个图有很多排列，求出让带宽最小的结点排列。

举例说明：

如图，最右边是无向图，下面两幅图都遵循这个连接方式，下面两幅图中，左图各结点的带宽分别是6,6,1,4,1,1,6,6。右图各结点带宽分别为5,3,1,4,3,5,1,4。

分析：n比较小，暴力求解，利用STL中next_permutation函数枚举全排列，逐个计算出其带宽，找出最小值即可。不过也并非完全不能优化，可以进行剪枝操作降低复杂度，如果发现某个排列中两个结点的距离大于当前找到的最优解，那么这个排列一定不是答案，直接剪掉。注意多组输入，要对数组初始化。否则会出错（我第一遍交没有初始化，结果交上去超时）。

复制代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int INF=0x7fffffff;
const int maxn=30;
int let[maxn],let_copy[maxn],pos[maxn];
vector<int> v[maxn];

int main() {
    //freopen("in.txt","r",stdin);
    string s;
    while(cin>>s&&s!="#"){
        memset(pos,0,sizeof(pos));
        for(int i=0;i<maxn;i++) v[i].clear();//初始化操作
        int k=0,ans=INF,ch;
        for(int i=0;i<s.size();i++){
            if(!i||s[i-1]==';') {
                ch=s[i]-'A';
                pos[s[i]-'A']=1;//pos数组标记了出现的字母
            }
            if(s[i]==':'){
                for(i=i+1;s[i]!=';'&&i<s.size();i++){
                    pos[s[i]-'A']=1;
                    v[ch].push_back(s[i]-'A');//vector保存各字母的连通性
                    v[s[i]-'A'].push_back(ch);
                }
            }
        }
        for(int i=0;i<26;i++)
            if(pos[i])let[k++]=i;
        do{
            int maximum=0;
            for(int i=0;i<k;i++){
                for(int j=i+1;j<k;j++){
                    for(int l=0;l<v[let[i]].size();l++){
                        if(v[let[i]][l]==let[j]) maximum=max(maximum,j-i);
                    }
                }
                if(maximum>ans) break;  //剪枝操作
            }
            if(ans>maximum){ 
                ans=maximum;
                memcpy(let_copy,let,sizeof(let)); //使用函数更快，保存答案
            }
        } while(next_permutation(let,let+k)); //枚举全排列
        for(int i=0;i<k;i++)
            cout<<(char)(let_copy[i]+'A')<<' ';
        cout<<"-> "<<ans<<endl;
    }
    return 0;
}

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
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int INF=0x7fffffff;
const int maxn=30;
int let[maxn],let_copy[maxn],pos[maxn];
vector<int> v[maxn];

int main() {
    //freopen("in.txt","r",stdin);
    string s;
    while(cin>>s&&s!="#"){
        memset(pos,0,sizeof(pos));
        for(int i=0;i<maxn;i++) v[i].clear();//初始化操作
        int k=0,ans=INF,ch;
        for(int i=0;i<s.size();i++){
            if(!i||s[i-1]==';') {
                ch=s[i]-'A';
                pos[s[i]-'A']=1;//pos数组标记了出现的字母
            }
            if(s[i]==':'){
                for(i=i+1;s[i]!=';'&&i<s.size();i++){
                    pos[s[i]-'A']=1;
                    v[ch].push_back(s[i]-'A');//vector保存各字母的连通性
                    v[s[i]-'A'].push_back(ch);
                }
            }
        }
        for(int i=0;i<26;i++)
            if(pos[i])let[k++]=i;
        do{
            int maximum=0;
            for(int i=0;i<k;i++){
                for(int j=i+1;j<k;j++){
                    for(int l=0;l<v[let[i]].size();l++){
                        if(v[let[i]][l]==let[j]) maximum=max(maximum,j-i);
                    }
                }
                if(maximum>ans) break;  //剪枝操作
            }
            if(ans>maximum){ 
                ans=maximum;
                memcpy(let_copy,let,sizeof(let)); //使用函数更快，保存答案
            }
        } while(next_permutation(let,let+k)); //枚举全排列
        for(int i=0;i<k;i++)
            cout<<(char)(let_copy[i]+'A')<<' ';
        cout<<"-> "<<ans<<endl;
    }
    return 0;
}