UVA - 140（Bandwidth ）（全排列+暴力）

92 阅读 0 评论 61 点赞

我是靠谱客的博主舒心铅笔，最近开发中收集的这篇文章主要介绍UVA - 140（Bandwidth ）（全排列+暴力），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：
给出一个n（n<=8）个节点的图G和一个节点的排列，定义节点i的带宽为相邻接点在排列中的最远距离。
分析：用全排列暴力做，先找出给出的序列中的所有字母，我用的set存贮（可以去掉重复的字母），这就是需要进行全排列的字符串，在每一个排列里找到带宽，然后输出其中的最小值即可。

做的时候总感觉没思路，其实就是自己傻，有时候不愿意深入地去想一个题，总是看完这个题感觉不会就去看另一个题，到头来那个题都做不出来，结果补提的时候才知道这个题这么简单。还有就是太依赖题解了（虽然这个题没看题解），结果养成了一看题就想看题解的坏毛病，其实题解可以看，但我感觉用来拓展思路挺好的，真正敲码的时候最好还是自己敲，这样才能提高自己的代码能力。
下面给出代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<vector>
#include<set>
#include<queue>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=30;
vector<char>G[maxn];
int main()
{
    string line;
    while(getline(cin,line)&&line[0]!='#') //输入
    {

        for(int i=0;i<maxn;i++)
            G[i].clear();
        set<char>q;             //用set去掉重复字母
        set<char>::iterator it;
        //遍历
        for(int i=0;i<line.length();i++)
        {
            if(line[i]==':')
            {
                for(int j=i+1;line[j]!=';'&&j<line.length();j++)
                {
                    int tmp=line[i-1]-'A';       //把：前面的用tmp表示你，后面的push进去

                     G[tmp].push_back(line[j]);
                }


            }
            if(line[i]>='A'&&line[i]<='Z')
             q.insert(line[i]);

        }
        char s[maxn];
        int len=0;
       //把序列放进s中，便于全排列
        for(it=q.begin();it!=q.end();it++)
        {

            s[len++]=*it;
        }


        int res=INF;    //记录最小带宽
        char rres[maxn]; //记录最小带宽时的序列
        do
        {
            int ans=0;
            for(int i=0;i<26;i++)
            {

                char ch1=i+'A';

                for(int j=0;j<G[i].size();j++)
                {
                    char ch2=G[i][j];

                    int pos1,pos2;
                    for(int k=0;k<len;k++)
                    {
                        if(s[k]==ch1)
                            pos1=k;
                        if(s[k]==ch2)
                            pos2=k;
                    }

                    int tmp=abs(pos1-pos2);

                    ans=max(ans,tmp);
                }
            }
            if(ans<res)
            {
                res=ans;
                for(int i=0;i<len;i++)
                    rres[i]=s[i];
            }

        }while(next_permutation(s,s+len));
        for(int i=0;i<len;i++)
        {
            printf("%c ",rres[i]);
        }
        printf("-> %dn",res);
    }
}