UVA - 140 Bandwidth C++【从这一篇开始好好写思路】

95 阅读 0 评论 63 点赞

我是靠谱客的博主洁净抽屉，最近开发中收集的这篇文章主要介绍UVA - 140 Bandwidth C++【从这一篇开始好好写思路】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：https://odzkskevi.qnssl.com/889829830aaae78906451977015d8af0?v=1532315931

思路：

我发现我每次ac后就懒得写思路了，所以这次一边写代码一边写思路。

这题看了半天终于读懂意思了。

这一段的意思相信大家都能读懂。所以题目给我们的输入是哪些字母互相之间有连线，这个连线的最长距离就是该字母的带宽，所有字母带宽的最大值就是该排列的带宽。

比如样例，A:FB;B:GC;D:GC;F:AGH;E:HD，如果我们按照ABCDEFGH来排列的话，那么带宽是5。而答案A B C F G D H E排列带宽是3，显然后者更优。而这题就是让我们寻找最优解。

所以……要怎么寻找。我是在刷紫书，所以看题时不小心就看到了刘汝佳的分析= =他说枚举全排列，然后剪枝。那就试试呗……全排列的话，紫书前几页有一个STL里的next_permutation()函数，在algorithm中。我们先把所有排列枚举一下，然后分别计算他们的带宽。因为带宽是要取所有结点之间距离的最大值，所以如果这两个结点直接距离已经超过上一个排列的带宽的话，我们就可以剪枝。

ok思路就到这里……我去写写看。不成的话再改，反正也不是直播23333

-----------居然ac了，我还以为会T。

这题输入挺麻烦的，我用map里面套set，本来是套vector的，但是vector会重复，所以用set比较好，并且set还自动排序。每一个结点对应的结点都放在它的set里。嘛，看代码就知道了。调用起来用迭代器就行。然后再用一个set来统计一共几个字母。

代码：

#include<iostream>
#include<algorithm>
#include<map>
#include<cstdio>
#include<string>
#include<cstring>
#include<set>
#include<cmath>
using namespace std;
#define INF 100000

map<int,set<int> >m;
set<int> s;
int ss[200];

int main()
{
    char a[100];
    char g[10];
    while(scanf("%s",&a)&&a[0]!='#')
    {
        m.clear();
        s.clear();
        memset(ss,0,sizeof(ss));
        memset(g,0,sizeof(g));
        int cur=(int)a[0];
        s.insert(a[0]);
        for(int i=1;i<strlen(a);)
        {
            if(a[i]==':')i++;
            else if(a[i]==';'){
                i++;
                s.insert(a[i]);
                cur=(int)a[i];
                i++;
            }
            else {m[cur].insert(a[i]);m[a[i]].insert(cur);s.insert(a[i]);i++;}
        }
        int k=0;
        set<int>::iterator it;
        for(it=s.begin();it!=s.end();it++)
        {
            ss[k]=*it;
            k++;
        }
        sort(ss,ss+k);

        int id[200];
        int mmax=INF;
        do{
            memset(id,0,sizeof(id));
            for(int i=0;i<k;i++){
                id[ss[i]]=i;
            }
            int mo=-INF;
            for(int i=0;i<k;i++){
                int mm=-INF;
                if(!m[ss[i]].empty()){
                    set<int>::iterator it;
                    for(it=m[ss[i]].begin();it!=m[ss[i]].end();it++)
                    {
                        mm=max(mm,abs(id[*it]-id[ss[i]]));
                        if(mm>=mmax)break;
                    }
                }
                mo=max(mo,mm);
                if(mo>=mmax)break;
            }
            if(mo>=mmax)continue;
            else {
                mmax=mo;
                for(int i=0;i<k;i++){
                    g[i]=(char)ss[i];
                }
            }
        }while(next_permutation(ss,ss+k));
        for(int i=0;i<k;i++){
            cout<<g[i]<<" ";
        }
        cout<<"-> "<<mmax<<endl;
    }
    return 0;
}