首页 > 代码库 > uva140 - Bandwidth

uva140 - Bandwidth

2024-07-09 09:34:57   222人阅读

题意：给一个最多8个结点的无向图，把结点重排后对于图中每条边(u,v)，u和v在排列中的最大距离称为该排列的带宽。求带宽最小的排列
算法：枚举全排列。需要注意的是本题的输入格式相对麻烦一点，需要仔细应对

学习点：

1. id和letter的映射关系处理

2. strtok函数使用方法

3.for(int i=0;i<n;i++) pos[P[i]]=i; 确认排列中元素位置

 

#include<cstdio>#include<cstring>#include<vector>#include<string>#include<algorithm>using namespace std;const int maxn=10;int id[256], letter[maxn];int n;void map_id_letter(char *p) {    n=0;    for(int c=‘A‘; c<=‘Z‘; c++) if(strchr(p, c))     {        id[c]=n;        letter[n]=c;        n++;    }}int main(){    char buff[256];    while(gets(buff) && buff[0]!=‘#‘)    {        map_id_letter(buff);        char*p=strtok(buff, ";");        vector<int> u,v;        while(p)        {            //printf("%s\n", p);            int t=p[0];            ++p;//跳过:            while(*(++p))            {                u.push_back(id[t]);                v.push_back(id[*p]);            }            p=strtok(0, ";");        }        int ans=n;        int P[maxn], bestP[maxn], pos[maxn];        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));        for(int i=0;i<n;i++)        {            printf("%c ", letter[bestP[i]]);        }        printf("-> %d\n", ans);    }        return 0;}


联系
我们