/*
题目不难,一次AC
题意:将图中各节点排在一条线上,依次找出各节点到相邻节点的最长距离,各节点最长距离的最大值即为带宽。输出带宽最小的序列,和带宽的值,如果出现多种情况,输出字典序最小的那种。
思路:深搜+回溯+状态存储
*/
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
char line[100];
bool G[30][30],visit[30];
char node[10],A[10],res[10];
int m;
int ans;
int cmp(const void *a,const void *b)
{
char *pa=(char *)a;
char *pb=(char *)b;
return *pa-*pb;
}
void dfs(int cur,int dep)
{
if(dep==m)
{
int temp=0;
for(int i=0;i<m;i++)
{
int k=0;
int a=A[i]-'A';
for(int j=0;j<m;j++)
if(i!=j)
{
int b=A[j]-'A';
if(G[a][b])
{
if(abs(i-j)>k)
k=abs(i-j);
}
}
if(k>temp)
temp=k;
}
if(temp<ans)
{
ans=temp;
memcpy(res,A,sizeof(A));
}
return;
}
for(int i=0;i<m;i++)
{
if(!visit[i])//排列式搜索,所以不需要G[][]值为1.
{
A[dep]=node[i];
visit[i]=1;
dfs(i,dep+1);
visit[i]=0;
}
}
}
int main()
{
//freopen("data.in","r",stdin);
while(1)
{
gets(line);
if(line[0]=='#') break;
int len=strlen(line);
int flag=0;
m=0;
memset(G,0,sizeof(G));
memset(visit,0,sizeof(visit));
int a,b;
for(int i=0;i<len;i++)
{
if(line[i]==';')
{
flag=0;
continue;
}
else if(line[i]==':')
{
flag=1;
continue;
}
else if(!visit[line[i]-'A'])
{
visit[line[i]-'A']=1;
node[m++]=line[i];
}
if(flag==0)
a=line[i]-'A';
else if(flag==1)
{
b=line[i]-'A';
G[a][b]=G[b][a]=1;
}
}
ans=1e9;
qsort(node,m,sizeof(node[0]),cmp);
memset(visit,0,sizeof(visit));
for(int i=0;i<m;i++)
{
A[0]=node[i];
visit[i]=1;
dfs(i,1);
visit[i]=0;
}
for(int i=0;i<m;i++)
printf("%c ",res[i]);
printf("-> %d\n",ans);
}
return 0;
}
分享到:
相关推荐
CUDA高性能编程之驱动程序编写之bandwidthTEST示例,适合初学者学习
带宽控制软件Bandwidth Splitter 1.07 破解版
Bandwidth Splitter v.1.39 for ISA Server 2004/2006
SoftPerfect Bandwidth Manager 使用教程
This paper describes a new control algorithm which can enhance the dynamics of a ... the bandwidth of the current controller was enhanced up to 250 Hz, and that of the speed controller was up to 50 Hz.
Bandwidth Splitter 2010 For Microsoft Forefront TMG 2010。 Bandwidth Splitter 1.32 最新破解版本。本人亲自测试可以使用。由于测试环境限制,是否支持10用户以上暂时没有测试。安装过程是一个英文的文本文档,...
经测试可用的Bandwidth Splitter 1.30 汉化破解版 5000用户,配合isa2004/2006可得到很强大的带宽控制功能
带宽管理软件Bandwidth_Splitter_使用指南
JESD238 2022 High Bandwidth Memory DRAM (HBM3).pdf
BandwidthTest是一款简单易用的绿色免费路由器转发率测试软件,主要用于测试指定路由器的芯片转发能力,转发率是衡量路由器性能的一个基本标准,也是评判路由器好坏的标准,使用BandwidthTest就可以一键进行测试了,...
在不便封锁的时候(例如内部客户使用HTTP/FTP下载),限制用户所使用的带宽是最好的办法,就是使用一款优秀的、强大的带宽控制软件-SoftPerfect Bandwidth Manager(BWM)。 BWM 是一个具有强大功能的带宽管理...
Artificial Bandwidth Extension method. codebook
Bollinger Bandwidth Delta 振荡指标
比较QoS服务策略的bandwidth和priority命令
clumsy-bandwidth-win64:在Windows下,模拟网络环境(丢包,延迟,带宽)的软件,亲测可用
Bandwidth Splitter v1.32 Fo _Microsof Forefront TMG_2010
Bandwidth_Splitter_v1.21和1.24破解版 都经过自己的服务器测试可用。。 在这个检测功能上还是很强大的说。。 这两个版本在一起的。
Bandwidth Splitter 1.37 for TMG 2010官方原版下载
A State-Space Technique for Ultrawide-Bandwidth Coherent Processing