UVa 140 - Bandwidth

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=76

类型： 回溯

原题：

Given a graph (V,E) where V is a set of nodes and E is a set of arcs in VxV, and anorderingon the elements in V, then thebandwidthof a nodevis defined as the maximum distance in the ordering betweenvand any node to which it is connected in the graph. The bandwidth of the ordering is then defined as the maximum of the individual bandwidths. For example, consider the following graph:

This can be ordered in many ways, two of which are illustrated below:

For these orderings, the bandwidths of the nodes (in order) are 6, 6, 1, 4, 1, 1, 6, 6 giving an ordering bandwidth of 6, and 5, 3, 1, 4, 3, 5, 1, 4 giving an ordering bandwidth of 5.

Write a program that will find the ordering of a graph that minimises the bandwidth.

题目大意：

给一张图， 对各个结点进行排列， 然后对于排列中的每一个点，求在图中与它相连的点在排列中的位置，算出它们在排列之间的最大距离， 最后，取这个排列中所有点的最大距离那个数为这个排列的bandwidth。

题目要我们求出所有排列中，bandwidth最小的那个排列，并输出这个排列和这个bandwidth

分析与总结：

比较简单的一道回溯题， 稍麻烦的是题目的输入。

只需要对求出所有排列的bandwidth，取其中最小的那个即可。注意可能会有多种方案，题目要求输出排列按字典序最小的那个方案。只要结点是按照顺序排列的，那么递归回溯出来的第一个答案一定是字典序最小的那个。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define MAXN 50
using namespace std;
int edge[MAXN], order[MAXN], minOrder[MAXN];
int G[MAXN][MAXN],loc[MAXN], minVal, cnt;
char str[20000];
bool vis[50], occur[30];

void read_in(){

    memset(occur, 0, sizeof(occur));
    memset(G, 0, sizeof(G));

    int len = strlen(str);
    str[len] = ';'; 
    str[len+1] = '\0';

    int i=0;
    int out[MAXN], top=0;

    while(i<strlen(str)){
        int u = str[i] - 'A';
        occur[u] = true;
        ++i; ++i;
        while(str[i]!=';'){
            int v = str[i]-'A';
            occur[v] = true;
            ++G[u][v];
            ++i;
        }
        ++i;
    }
    cnt = 0;
    for(int i=0; i<28; ++i) if(occur[i]){
        edge[cnt++] = i;
    }
}

int counter(){
  	int totalMax = -999;
    for(int i=0; i<cnt; ++i){
        int maxVal = -999;
        for(int j=0; j<cnt; ++j)if(G[edge[order[i]]][edge[j]]){
           int pos = loc[edge[j]];
            if(abs(pos-i) > maxVal) maxVal=abs(pos-i);
        }
        if(maxVal > totalMax) totalMax = maxVal;
    }
    return totalMax;
}

void search(int cur){
    if(minVal==1) return;
    for(int i=0; i<cnt; ++i)if(!vis[i]){
        vis[i] = true;
        order[cur] = i;
        loc[edge[i]] = cur;
        search(cur+1);
        vis[i] = false;
    }
    if(cur==cnt){
        int totalMax = counter();

        if(totalMax < minVal) {
            minVal = totalMax;
            memcpy(minOrder, order, sizeof(order));
        }
    }
}


int main(){
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif
    while(gets(str)){
        if(str[0]=='#') break;

        read_in();

        minVal = 9999999;
        memset(vis, 0, sizeof(vis));
        search(0);

        for(int i=0; i<cnt; ++i) printf("%c ",edge[minOrder[i]]+'A');
        printf("-> %d\n", minVal); 
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

    

  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)