Uva140 Bandwidth 【dfs回溯+剪枝】【例题7-6】

题目：Bandwidth

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

思路：

（1）处理输入：将给出的字符串用二维数组表示成图

（2）标准的回溯dfs，将给出的结点进行全排列，筛选最小带宽。

（3）剪枝：在进行排列时，当前的结点如果与之前的结点的距离大于当前的最优值，则无需再递归排列，因为此序列已经不可能为最优解了。剪掉。

参考：入门经典-例题7-6-P197

代码：

#include <iostream>#include <stdio.h>#include <string.h>using namespace std;char str[100];int g[30][30],visit[30],ans,number;int PRt[10];void dfs(int steps, int seq[]){    if(steps == number){//满足个数        int maxv = 0;        for(int i=0;i<number;i++)//进行寻找本次排列的带宽            for(int j=i+1;j<number;j++)                if(g[seq[i]][seq[j]]) maxv = max(maxv,j-i);        if(ans > maxv){//保留最大值            ans = maxv;            for(int i=0;i<number;i++) prt[i] = seq[i];//保存序列        }        return;    }    for(int i=0;i<26;i++){        if(visit[i]){            int ok = 1;            for(int j=0;j<steps;j++)//判断当前结点与之前的结点距离，如果大于当前最优值，就无需再递归排列了，剪枝                if(g[i][seq[j]])//存在边                    if(steps-j > ans){ok = 0;break;}//如果大于最优解即跳出            if(ok){                seq[steps] = i;                visit[i] = 0;                dfs(steps+1,seq);                visit[i] = 1;            }        }    }return ;}int main(){    while(scanf("%s",str)!=EOF && str[0] != '#'){        int i=0;        memset(g,0,sizeof(g));        memset(visit,0,sizeof(visit));        while(str[i]!='/0'){//处理输入，用二维数组g表示出来图            if(str[i] == ':'){                int s = str[i-1] - 'A';                visit[s] = 1;                i++;                while(str[i] != ';' && str[i] != '/0'){                    g[s][str[i] - 'A'] = 1;                    g[str[i] - 'A'][s] = 1;                    visit[str[i] - 'A'] = 1;                    i++;                }            }            else i++;        }        number = 0;        for(int i=0;i<26;i++) if(visit[i]) number++;//计算结点个数        ans = 99999999;        int temp[10];        dfs(0,temp);        for(int i=0;i<number;i++) printf("%c ",prt[i]+'A');        printf("-> %d/n",ans);    }return 0;}