UVa 140 带宽

题意：给出一个n个结点的图G和一个结点的排列，定义结点的带宽为i和相邻结点在排列中的最远距离，求出让带宽最小的结点排列。

思路:用STL的next_permutation来做确实是很方便，适当剪枝一下就可以了，不过我不明白的是为什么我用string字符串会超时...

 1 #include<iostream>
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int a[30], c[30];
 8 int ans[30];
 9 int map[30][30];
10 char str[500];
11 
12 int main()
13 {
14     //freopen("D:\txt.txt", "r", stdin);
15     int l, k, maxn,n;
16     while (gets(str) )
17     {
18         if (str[0] == '#') break;
19         memset(map, 0, sizeof(map));
20         memset(a, 0, sizeof(a));
21         memset(ans, 0, sizeof(ans));
22         memset(c, 0, sizeof(c));
23         l = strlen(str);25         for (int i = 0; i < l; i++)
26         {
27             if (str[i] == ':')
28             {
29                 int t = str[i - 1] - 'A';
30                 a[t] = 1;
31                 for (k = i + 1; str[k] != ';' && k < l; k++)
32                 {
33                     int p = str[k] - 'A';
34                     a[p] = 1;
35                     map[t][p] = map[p][t] = 1;
36                 }
37                 i = k;
38             }
39         }
40 
41 
42         n = 0;
43         for (int i = 0; i < 26; i++)
44         {
45             if (a[i])
46                 c[n++] = i;
47         }
48         maxn = 10000;
49         do
50         {
51             int sum = 0;
52             int ok = 1;
53             for (int i = 0; i < n; i++)
54             {
55                 for (int j = i + 1; j < n; j++)
56                 {
57                     if (map[c[i]][c[j]])
58                     if (j - i>sum)
59                         sum = j - i;
60                     if (sum>=maxn)  { ok = 0; break; }
61                 }
62                 if (!ok)  break;
63             }
64             
65             if (sum < maxn)
66             {
67                 maxn = sum;
68                 memcpy(ans, c, sizeof(c));
69             }
70         } while (next_permutation(c, c + n));
71         for (int i = 0; i < n; i++)
72         {
73             char s = 'A' + ans[i];
74             cout << s << " ";
75         }
76         cout << "-> " << maxn << endl;
77     }
78     return 0;
79 }