frank

UVa140解题报告(枚举,暴力)
题目描述给出一个有n(n≤8)个节点的图和一个结点的排列。结点i的带宽bi的定义为结点i和相邻结点在排列中的最远距...
扫描右侧二维码阅读全文
28
2018/07

UVa140解题报告(枚举,暴力)

题目描述

给出一个有n(n≤8)个节点的图和一个结点的排列。结点i的带宽bi的定义为结点i和相邻结点在排列中的最远距离,而所有bi的最大值就是整个图的带宽。

例如,给出如下的图:

宽带图

此图可以给出多种排序,其中两个排序,图示如下:

各种排序时的带宽

左图中各个节点的带宽分别为:6,6,1,4,1,1,6,6,那么排列的带宽为6

右图中各个节点的带宽分别为:5,3,1,4,3,5,1,4,那么排列的带宽是5

写出一个程序,给定一个图,求出该图的一种排序使其带宽最小。

输入格式

输入多行,每行代表一个图,当一行是一个单独的“#”时,代表输入结束。

对于每个图的输入,都包含一系列由“;”隔开的记录,每个记录包含一个结点名,接着是一个“:”,然后是这个结点的邻居结点名,都用大写字母表示,范围是“A”到“Z”。每个图的结点数都不会超过8个。

输出格式

对于输入的每一图输出一行,列出排序的结点,然后是一个箭头(->),然后是该排序的带宽值,所有项用空格隔开(如样例所示)。如果同一个带宽有多种排序方法,取字母序最小的一种排序。

输入输出样例

输入样例

A:FB;B:GC;D:GC;F:AGH;E:HD
#

输出样例

A B C F G D H E -> 3

分析与思路

难度:提高/省选-

说到排列,很容易想到枚举排列,将字母映射成id(数字),生成每种排列,分别计算带宽,取最小值。用两个vector存储相邻的节点,这样一来,这道题就很easy啦!!!

题解

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

const int maxn = 10;
int id[256], letter[maxn];

int main() {
  char input[1000];
  while(scanf("%s", input) == 1 && input[0] != '#') {
    // 计算结点个数并给字母编号
    int n = 0;
    for(char ch = 'A'; ch <= 'Z'; ch++)
      if(strchr(input, ch) != NULL) {
        id[ch] = n++;
        letter[id[ch]] = ch;
      }

    // 处理输入
    int len = strlen(input), p = 0, q = 0;
    vector<int> u, v;
    for(;;) {
      while(p < len && input[p] != ':') p++;
      if(p == len) break;
      while(q < len && input[q] != ';') q++;
      for(int i = p+1; i < q; i++) {
        u.push_back(id[input[p-1]]);
        v.push_back(id[input[i]]);
      }
      p++; q++;
    }

    // 枚举全排列
    int P[maxn], bestP[maxn], pos[maxn], ans = n;
    for(int i = 0; i < n; i++) P[i] = i;
    do {
      for(int i = 0; i < n; i++) pos[P[i]] = i; // 每个字母的位置
      int bandwidth = 0;
      for(int i = 0; i < u.size(); i++)
        bandwidth = max(bandwidth, abs(pos[u[i]] - pos[v[i]])); // 计算带宽
      if(bandwidth < ans) {
        ans = bandwidth;
        memcpy(bestP, P, sizeof(P));
      }
    } while(next_permutation(P, P+n)); //排列神器,要调用<algorithm>

    // 输出
    for(int i = 0; i < n; i++) printf("%c ", letter[bestP[i]]);
    printf("-> %d\n", ans);
  }
  return 0;
}
Last modification:July 29th, 2018 at 10:19 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment