UVA - 140 Bandwidth-白红宇

UVA - 140 Bandwidth

阅读量：3904 次

发布时间：2019-05-23

本文共 983 字，大约阅读时间需要 3 分钟。

题意：

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

输入：

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

输出：

A B C F G D H E -> 3

思路：

如果直接枚举全序列的话，效率不高。所以需要剪枝。

(1)如果未排列完的序列已经大于等于ans了，则剪掉。

(2) 如果一个顶点现在的位置加上那些还和它相连且没有被安排的顶点的数量加上现在的位置大于ans的话，则剪掉。

代码如下：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       using namespace std;const int maxn=30;char a[105];int vis[30];int loc[10];int g[10][10];int arr[10];int temp[10];int cnt;int ans;map
        
         ma,ma1;void dfs (int num,int tans,int temp[]){ if(tans>=ans) return; if(num==cnt) { if(ans>tans) { ans=tans; for (int i=0;i
         
          =ans) { ok=0; break; } tans=max(tans,w); } } if(ok) { loc[i]=num; dfs(num+1,tans,temp); loc[i]=-1; } } }}int main(){ while (scanf("%s",a)!=EOF) { ma.clear(); ma1.clear(); cnt=0; if(a[0]=='#'&&strlen(a)==1) break; memset (vis,0,sizeof(vis)); memset (g,0,sizeof(g)); memset (loc,-1,sizeof(loc)); int len=strlen(a); for (int i=0;i
          
            %d\n",ans); } return 0;}

转载地址：http://jwoen.baihongyu.com/

你可能感兴趣的文章