UVA140 ——bandwidth(搜索)

时间:2021-10-30 12:13:29

Given a graph (V,E) where V is a set of nodes and E is a set of arcs in VxV, and an ordering on the elements in V, then the bandwidth of a node v is defined as the maximum distance in the ordering between v and any node to which it is connected in the graph. The bandwidth of the ordering is then defined as the maximum of the individual bandwidths. For example, consider the following graph:

UVA140 ——bandwidth(搜索)

This can be ordered in many ways, two of which are illustrated below:

UVA140 ——bandwidth(搜索)

For these orderings, the bandwidths of the nodes (in order) are 6, 6, 1, 4, 1, 1, 6, 6 giving an ordering bandwidth of 6, and 5, 3, 1, 4, 3, 5, 1, 4 giving an ordering bandwidth of 5.

Write a program that will find the ordering of a graph that minimises the bandwidth.

Input

Input will consist of a series of graphs. Each graph will appear on a line by itself. The entire file will be terminated by a line consisting of a single #. For each graph, the input will consist of a series of records separated by `;'. Each record will consist of a node name (a single upper case character in the the range `A' to `Z'), followed by a `:' and at least one of its neighbours. The graph will contain no more than 8 nodes.

Output

Output will consist of one line for each graph, listing the ordering of the nodes followed by an arrow (->) and the bandwidth for that ordering. All items must be separated from their neighbours by exactly one space. If more than one ordering produces the same bandwidth, then choose the smallest in lexicographic ordering, that is the one that would appear first in an alphabetic listing.

Sample input

A:FB;B:GC;D:GC;F:AGH;E:HD
#

Sample output

A B C F G D H E -> 3

求出排列好后,相连的两个值之间存在的最大值,然后找出最大值最小的那一组

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int maps[30][30];
int hav[30];
int p[10],a[10];
int ans[10],n,pmax,sum;
int work() //如果相连,求它们之间距离的最大值
{
int tmax = 0;
for(int i=1; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(maps[a[i]][a[j]])
{
if(j - i>tmax)
tmax=j-i;
}
}
}
return tmax;
}
void dfs(int cur)
{
int flag;
if(cur==n)
{
sum=work();
if(pmax>sum) //找出最大距离最小的那一组
{
pmax=sum;
memcpy(ans,a,sizeof(a));
}
return ;
}
else
{
for(int i=1; i<n; i++)
{
flag=1;
a[cur]=p[i];
for(int j=1; j<cur; j++)
{
if(a[j]==a[cur])
{
flag=0;
break;
}
}
if(flag)
dfs(cur+1);
}
}
}
int main()
{
char str[100];
char c;
int len,i,pre,now;
while(gets(str)&&strcmp(str,"#"))
{
n=1,pmax = 0x3f3f3f3f;
len=strlen(str);
memset(maps,0,sizeof(maps));
memset(hav,0,sizeof(hav));
memset(p,0,sizeof(p));
for(i=0; i<len; i++)
{
c=str[i];
if(str[i+1]==':')
{
pre=c-'A'+1;
hav[pre]++;
}
else if(c>='A'&&c<='Z')
{
now=c-'A'+1;
hav[now]++;
maps[now][pre]=maps[pre][now]=1;
}
}
for(i=0; i<27; i++)
{
if(hav[i])
p[n++]=i;
}
dfs(1);
for(i=1; i<n; i++)
printf("%c ",ans[i]+'A'-1);
printf("-> %d",pmax);
printf("\n");
}
return 0;
}

  

UVA140 ——bandwidth(搜索)的更多相关文章

  1. uva140 - Bandwidth

    Bandwidth Given a graph (V,E) where V is a set of nodes and E is a set of arcs in VxV, and an orderi ...

  2. UVa140 Bandwidth 小剪枝&plus;双射小技巧&plus;枚举全排列&plus;字符串的小处理

    给出一个图,找出其中的最小带宽的排列.具体要求见传送门:UVa140 这题有些小技巧可以简化代码的编写. 本题的实现参考了刘汝佳老师的源码,的确给了我许多启发,感谢刘老师. 思路: 建立双射关系:从字 ...

  3. Uva140 Bandwidth 全排列&plus;生成测试法&plus;剪枝

    参考过仰望高端玩家的小清新的代码... 思路:1.按字典序对输入的字符串抽取字符,id[字母]=编号,id[编号]=字母,形成双射       2.邻接表用两个vector存储,存储相邻关系     ...

  4. UVa140 Bandwidth 【最优性剪枝】

    题目链接:https://vjudge.net/contest/210334#problem/F  转载于:https://www.cnblogs.com/luruiyuan/p/5847706.ht ...

  5. 递归回溯 UVa140 Bandwidth宽带

    本题题意:寻找一个排列,在此排序中,带宽的长度最小(带宽是指:任意一点v与其距离最远的且与v有边相连的顶点与v的距离的最大值),若有多个,按照字典序输出最小的哪一个. 解题思路: 方法一:由于题目说结 ...

  6. UVA-140 Bandwidth (回溯&plus;剪枝)

    题目大意:求一个使带宽最小的排列和最小带宽.带宽是指一个字母到其相邻字母的距离最大值. 题目分析:在递归生成全排列的过程中剪枝,剪枝方案还是两个.一.当前解不如最优解优时,减去:二.预测的理想解不必最 ...

  7. 7-6 Bandwidth UVA140

    没有清空向量导致debug了好久 这题难以下手  不知道怎么dfs 原来是用排序函数. letter[n]=i; id[i]=n++; 用来储存与设置标记十分巧妙 for(;;) { while(s[ ...

  8. uva 140 bandwidth (好题) ——yhx

     Bandwidth  Given a graph (V,E) where V is a set of nodes and E is a set of arcs in VxV, and an orde ...

  9. UVa OJ 140 - Bandwidth &lpar;带宽&rpar;

    Time limit: 3.000 seconds限时3.000秒 Problem问题 Given a graph (V,E) where V is a set of nodes and E is a ...

随机推荐

  1. Android Fragment &lpar;二&rpar; 实例2

    由于看客的要求,我就把读者所要的写出来. 由于上一篇是每一个Fragment 实例了同一个layout.xml ,造成了读者的困惑,这篇我就让每一个Fragment 加载一个不同的layout.xml ...

  2. npm穿墙

    GWF 很给力,很多东西都能墙掉,但是把 npm 也纳入黑名单,不知道 GWFer 是怎么想的.FQ翻了好多年了,原理其实也挺简单的,proxy 嘛! » 方法一 A) 国内源,http://cnpm ...

  3. 内省与JavaBean

    概述 JavaBean代表一类特殊的Java类,这种类主要用来存储和传递属性信息,JavaBean中的方法主要用于设置和获取这些私有属性,他们有一定的命名规则,我们可以把它们想象为一个侧重属性信息的类 ...

  4. Set up your first C&num; test with NUnit or resharper

    此链接为一种方式,用Nunit单元测试驱动测试代码 http://relevantcodes.com/using-nunit-to-execute-selenium-webdriver-tests/ ...

  5. redmine安装插件流程

    1.redmine用一键安装即可2.进入C:\Bitnami\redmine-3.1.1-1\,执行use_redmine.exe,进入dos系统 不能用cmd进入.3.把文件拷贝到C:\Bitnam ...

  6. shell基础——二元比较操作符

    二元比较操作符,比较变量或者比较数字.注意数字与字符串的区别. 整数比较 -eq 等于,如:if [ "$a" -eq "$b" ]-ne 不等于,如:if [ ...

  7. Mockito单元测试实战

    最近使用Mockito完成了几个简单的测试,写个博客mark一下: 第一种模拟web请求 @SpringBootTest @RunWith(SpringRunner.class) @WebAppCon ...

  8. STL——set

    (转) 1.关于set C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用 ...

  9. mysql外键的三种关系

    因为有foreign key的约束,使得两张表形成了三种了关系: 多对一 多对多 一对一 一对多或多对一 create table press( id int primary key auto_inc ...

  10. Android之Android apk动态加载机制的研究(二):资源加载和activity生命周期管理

    转载请注明出处:http://blog.csdn.net/singwhatiwanna/article/details/23387079 (来自singwhatiwanna的csdn博客) 前言 为了 ...