UVa 140 - Bandwidth

傳送門UVa 140 - Bandwidth

題意是讓我們找出在給出的結點中相鄰結點的最大距離。

一開始我想用回溯法構造排列，然後存在一個數組裡，之後再算。。可是這樣二維數組要開到40000多了，不太可能實作。

參考了GooMaple的解題報告。非常好的思路，又可以讓我回味一個晚上了╮(╯▽╰)╭

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

int G[30][30];
int alpha[30], node[10], ans[10];

void GetSequ(int cur);

int main()
{
    //freopen("input.txt", "r", stdin);
    int i, j;
    char str[100], ch;
    int cnt, minAllMax, maxLen;
    while (fgets(str, 100, stdin))
    {
        if (str[0] == '#')
            break;
        memset(G, 0, sizeof(G));
        memset(alpha, 0, sizeof(alpha));
        cnt = 0;
        minAllMax = (1 << 30) - 1;
        int len = strlen(str);
        //下面兩個循環是為了統計出結點個數和結點所代表的編号，一個字母對應一個編号
        for (i = 0; i < len; i++)
            if (isalpha(str[i]))
                alpha[str[i] - 'A'] = 1;
        for (i = 0; i < 26; i++)
            if (alpha[i])
                node[cnt++] = i;
        i = 0;
        //下面是讀取字元串部分，大家可以自由發揮。。
        while (true)
        {
            while (str[i] != ':')
                i++;
            ch = str[i - 1];
            i++;
            while (str[i] != ';' && str[i] != '\n')
            {
                G[ch - 'A'][str[i] - 'A'] = G[str[i] - 'A'][ch - 'A'] = 1;
                i++;
            }
            if (str[i] == '\n')
                break;
        }
        do
        {
            maxLen = -1;
            for (int i = 0; i < cnt; i++)
                for (j = i + 1; j < cnt; j++)
                {
                    if (G[node[i]][node[j]] && j - i > maxLen)
                        maxLen = j - i;
                    if (maxLen > minAllMax) //剪枝
                        break;
                }
            if (maxLen < minAllMax)
            {
                minAllMax = maxLen;
                memcpy(ans, node, sizeof(node));
            }
        } while (next_permutation(node, node + cnt));
        for (i = 0; i < cnt; i++)
            printf("%c ", ans[i] + 'A');
        printf("-> %d\n", minAllMax);
    }
    return 0;
}