uva 140 - Bandwidth

点击打开链接

题目意思：给定n个节点，（n<=8），节点的编号为A～Z 来表示，要求找到一个节点的序列，使得该序列最大的节点的Bandwidth为所有序列中的最小值，（节点的Bandwidth是指和它所连接的点中和它距离最大的值）。

解题思路：由于最多只有8个节点，那么可以枚举这个解空间的所有情况，然后找到其中的最有解并且记录下它的节点顺序，那么我们可以通过求全排列的方法去一一枚举这些排列

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
using namespace std;
const int MAXN = 100000;

int k, cur, ans;
int vis[8];//存储节点的编号，通过编号来映射节点
int mark[30][30]; //用来标记节点和哪些节点有连接
int Minsum[MAXN][8];//用来记录每一个排列的节点的顺序
int Min;

//计算最小值的函数
void Minfun() {
    int tempmax[8];//临时存储每一个点的最大值
    int T, Tmax = 0;//T存储当前节点和另外节点的距离，Tmax存储一个点中的最大距离（后面求一个排列的最大值）
    memset(tempmax, 0, sizeof (tempmax)); //初始话为0
    for (int i = 0; i < k; i++) {//枚举这个序列的点
        Tmax = 0;
        for (int j = 1; j <= 26; j++) {
            if (mark[vis[i]][j]) {//找打一个点的匹配点的最大的值
                for (int t = 0; t < k; t++) {//找匹配点的位置
                    if (j == vis[t]) {
                        T = abs(i - t); //找到位置的距离
                        break;
                    }
                }
                if (Tmax < T)
                    Tmax = T;
            }
        }
        tempmax[i] = Tmax;
    }
    Tmax = 0;
    for (int i = 0; i < k; i++) {//求出该种排列的最大值
        if (Tmax < tempmax[i]) {
            Tmax = tempmax[i];
        }
    }
    if (Min > Tmax) {//更新Min的值
        ans = cur;//记录位置
        Min = Tmax;
    }
}

//处理函数

void solve() {
    Min = 100000000;
    cur = 0;
    for (int i = 0; i < k; i++)//必须先保存到Minsum[0]里，不然调用了next_permutation(vis, vis + k)将直接跳到下一个排列
        Minsum[0][i] = vis[i];
    Minfun();//求出Min
    ++cur;
    while (next_permutation(vis, vis + k)) {//得到全排列
        for (int i = 0; i < k; i++)
            Minsum[cur][i] = vis[i]; //把序列存入mark数组里面
        Minfun();//判断是否最小值
        cur++;
    }
}

//输出函数

void output() {
    for (int i = 0; i < k; i++)
        printf("%c ", Minsum[ans][i] + 64);
    printf("-> %d\n", Min);
}
//主函数

int main() {
    int i, j;
    char c;
    int Tvis[27];
    string str;
    while (cin >> c) {
        if (c == '#')
            break;
        memset(mark, 0, sizeof (mark));
        memset(Tvis, 0, sizeof (Tvis));
        memset(Minsum, 0, sizeof (Minsum));
        i = c - 64;
        vis[0] = i;
        Tvis[i] = 1;
        k = 1;
        cin >> str;
        //处理字符串
        for (j = 0; j < str.size(); ++j) {
            if (str[j] == ':') {
                continue;
            }
            if (str[j] == ';') {
                ++j;
                i = str[j] - 64;
                if (isupper(str[j])) {
                    if (Tvis[str[j] - 64] == 0) {
                        Tvis[str[j] - 64] = 1;
                        vis[k] = str[j] - 64;
                        ++k;
                    }
                }
                continue;
            }
            if (isupper(str[j])) {
                if (Tvis[str[j] - 64] == 0) {
                    Tvis[str[j] - 64] = 1;
                    vis[k] = str[j] - 64;
                    ++k;
                }
            }
            mark[i][str[j] - 64] = 1;//标记为1，说明两个节点有连接
        }
        sort(vis, vis + k); //必须先对数组先排序
        solve();
        output();
    }
}