Problem Solving►UVa

UVa 140 - Bandwidth

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

先給定圖，接著找出一組特定排序，使得圖中所有的邊，最大權重為最小。(只要兩點可連通，就要去判斷它在排序內的間隔。)
注意此權重為 排序內的間隔。

Solution

可以先將用到的字母依序編號，字典序小的先，方便待會做排列。
要窮舉出全部的排列，可以採用 DFS 或是 std::next_permutation 。
接著只需找出排列中最大的邊，再從所有排列之中找一組最小的。

找排列中最大的邊:

for (i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if (adjM[map[order[i]]][map[order[j]]] && abs(i - j) > max)
            max = abs(i - j);

Code

UVa 140(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<cstdio>
#include<algorithm>
#define N 26
using namespace std;

bool adjM[N][N];
int ans[8], map[N];
int solve(int n);
int main()
{
    bool isNode[N];
    char str[100];
    while (gets(str) && str[0] != '#')
    {
        int i = 0, idx = 0, u;
        for (i = 0; i < N; i++)
            map[i] = -1, isNode[i] = false;
        for (i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                adjM[i][j] = false;

        i = 0;
        while (str[i])
        {
            u = str[i] - 'A';
            if (!isNode[u])
            {
                map[idx++] = str[i] - 'A';
                isNode[u] = true;
            }

            i += 2;//':'

            while (str[i] != ';'&&str[i])
            {
                int v = str[i] - 'A';
                if (!isNode[v])
                {
                    map[idx++] = v;
                    isNode[v] = true;
                }

                adjM[u][v] = true;
                i++;
            }

            if (str[i])
                i++;
        }

        int min = solve(idx);

        for (i = 0; i < idx; i++)
            printf("%c ", map[ans[i]] + 'A');

        printf("-> %d\n", min);
    }

    return 0;
}
int solve(int n)
{
    int order[8];
    bool next = true;
    int i, min_bw = 100;

    sort(map, map + n);
    for (i = 0; i < n; i++)
        order[i] = i;

    while (next)
    {
        int max = 0;
        for (i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (adjM[map[order[i]]][map[order[j]]] && abs(i - j) > max)
                    max = abs(i - j);

        if (max < min_bw)
        {
            min_bw = max;
            for (i = 0; i < n; i++)
                ans[i] = order[i];
        }

        next = next_permutation(order, order + n);
    }

    return min_bw;
}

DFS

UVa 140(2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<cstdio>
#include<algorithm>
#define N 26

int min_bw;
bool adjM[N][N], isNode[N];
int ans[8], map[N];
void dfs(int n, int now);
int main()
{
    char str[100];
    while (gets(str) && str[0] != '#')
    {
        min_bw = 1e9;
        int i = 0, idx = 0, u;
        for (i = 0; i < N; i++)
            map[i] = -1, isNode[i] = false;
        for (i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                adjM[i][j] = false;

        i = 0;
        while (str[i])
        {
            u = str[i] - 'A';
            if (!isNode[u])
            {
                map[idx++] = str[i]-'A';
                isNode[u] = true;
            }

            i += 2;//':'

            while (str[i] != ';'&&str[i])
            {
                int v = str[i] - 'A';
                if (!isNode[v])
                {
                    map[idx++] = v;
                    isNode[v] = true;
                }

                adjM[u][v] = true;
                i++;
            }

            if (str[i])
                i++;
        }
        std::sort(map, map + idx);

        dfs(idx, 0);
        for (i = 0; i < idx; i++)
            printf("%c ", map[ans[i]] + 'A');

        printf("-> %d\n", min_bw);
    }

    return 0;
}
void dfs(int n, int now)
{
    static int order[8];
    static bool used[8];
    int i;

    if (!now)//init
    {
        for (i = 0; i < n; i++)
            used[i] = false;
    }

    if (now == n)
    {
        int max = 0;
        for (i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (adjM[map[order[i]]][map[order[j]]] && std::abs(i - j) > max)
                    max = std::abs(i - j);

        if (max < min_bw)
        {
            min_bw = max;
            for (i = 0; i < n; i++)
                ans[i] = order[i];
        }
    }
    else
    {
        for (i = 0; i < n; i++)
        {
            if (!used[i])
            {
                used[i] = true;
                order[now] = i;
                dfs(n, now + 1);
                used[i] = false;
            }
        }
    }

}