題目：Bandwidth

題意：給出一個(gè)n（n≤8）個(gè)結(jié)點(diǎn)的圖G和一個(gè)結(jié)點(diǎn)的排列，定義結(jié)點(diǎn)i的帶寬b(i)為i和相鄰結(jié)點(diǎn)在排列中的最遠(yuǎn)距離，而所有b(i)的最大值就是整個(gè)圖的帶寬。 給定圖G，求出讓帶寬最小的結(jié)點(diǎn)排列。

思路：

（1）處理輸入：將給出的字符串用二維數(shù)組表示成圖

（2）標(biāo)準(zhǔn)的回溯dfs，將給出的結(jié)點(diǎn)進(jìn)行全排列，篩選最小帶寬。

（3）剪枝：在進(jìn)行排列時(shí)，當(dāng)前的結(jié)點(diǎn)如果與之前的結(jié)點(diǎn)的距離大于當(dāng)前的最優(yōu)值，則無(wú)需再遞歸排列，因?yàn)榇诵蛄幸呀?jīng)不可能為最優(yōu)解了。剪掉。

參考：入門(mén)經(jīng)典-例題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){//滿(mǎn)足個(gè)數(shù)        int maxv = 0;        for(int i=0;i<number;i++)//進(jìn)行尋找本次排列的帶寬            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++)//判斷當(dāng)前結(jié)點(diǎn)與之前的結(jié)點(diǎn)距離，如果大于當(dāng)前最優(yōu)值，就無(wú)需再遞歸排列了，剪枝                if(g[i][seq[j]])//存在邊                    if(steps-j > ans){ok = 0;break;}//如果大于最優(yōu)解即跳出            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'){//處理輸入，用二維數(shù)組g表示出來(lái)圖            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++;//計(jì)算結(jié)點(diǎn)個(gè)數(shù)        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;}