UVA 140 Bandwidth，uva140bandwidth

UVA 140 Bandwidth，uva140bandwidth

題意：

　　給出一個n個節點的圖G，和一個節點的排列，定義節點i的帶寬為i和相鄰節點在排列中的最遠距離，而所有帶寬的最大值就是圖的帶寬，求讓圖的帶寬最小的排列。

分析：

　　列出所有可能的排列，記錄當前找到的最小帶寬。如果有某兩個節點的距離大於或等於最小帶寬，這種排列減掉。

代碼：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int use[27]//記錄那個字母被使用;
int node[9],save[9];
int map[27][27];
int cnt,maxn;
char a[500];
int main()
{
    int i,j,k;
    while(gets(a))
    {
        if(a[0]=='#')
            break;
        memset(use,0,sizeof(use));
        memset(map,0,sizeof(map));
        int len=strlen(a);
        maxn=10;
        cnt=0;
        int flag=0;
        for(i=0,flag=0;i<len;i++)
        {
            if(a[i]>='A'&&a[i]<='Z')
                use[a[i]-'A']=1;
            int c;
            if(a[i]==':')
            {
                c=a[i-1]-'A';
                flag=1;
            }
            else if(a[i]>='A'&&a[i]<='Z'&&flag)
            {
                map[c][a[i]-'A']=map[a[i]-'A'][c]=1;
            }
            else if(a[i]==';')
                flag=0;
        }
        for(i=0;i<26;i++)
            if(use[i]==1)
                node[cnt++]=i;
        do
        {
            int num=0;
            for(i=0;i<cnt;i++)
            {
                for(j=i+1;j<cnt;j++)
                {
                    if(map[node[i]][node[j]])
                        if(abs(j-i)>num)
                            num=abs(j-i);
                }
                if(num>maxn)
                    break;
            }
            if(maxn>num)
            {
                maxn=num;
                memcpy(save,node,sizeof(node));
            }
        }
        while(next_permutation(node,node+cnt));
        for(i = 0; i < cnt; i++)
            printf("%c ", save[i] + 'A');
        printf("-> %d\n", maxn);
    }
}