UVA140 宽带剪枝+映射铺展+题意

93 阅读 0 评论 62 点赞

我是靠谱客的博主稳重冬日，最近开发中收集的这篇文章主要介绍UVA140 宽带剪枝+映射铺展+题意，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：题目给你每个节点和它所之间连接的对象，距离为1.给出所有节点的排列，求每个排列所有可直接连接的节点间距离的最大值中的最小值。

思路：枚举全排列，判断每个相连结点的距离，剪枝优化

反思：

1.对于题意没有理解清楚，TLE到怀疑人生，后来恍然醒悟，给出的节点不一定是按顺序升序给出的，比如我可以给出A D E F,而不是ABCDEF,所以这里就要记录一下出现的节点，而不能单单是求最大的字符orz（哭）

2.这里每一个节点直接相连的点有一个映射关系，愿来考虑过用map存父节点和子节点，但是这样在循环里就会出现二重循环分别枚举父节点和子节点，肯定超时。所以不如一个个把父节点和子节点对应铺展开来，child[i]对应的父节点就是root[i]，一重循环搞定。

3.memcpy函数的使用：(cstring)

memcyp(a,b,n);复制b中n个子节到a中

与strcpy相比，memcpy并不是遇到''就结束，而是一定会拷贝完n个字节。

memcpy用来做内存拷贝，你可以拿它拷贝任何数据类型的对象，可以指定拷贝的数据长度。

例：

char a[100], b[50];

memcpy(b, a,sizeof(a)); //注意如用sizeof(a)，可能会造成b的内存地址溢出。

//strcpy就只能拷贝字符串了，它遇到''就结束拷贝；例：

char a[100], b[50]；

strcpy(a,b);

注：a,b不一定是数组，任意可读写的空间均可！

代码：

#include <iostream>
#include<bits/stdc++.h>
#define INF 0x7fffffff
using namespace std;
char str[100];//输入
int root[100];//父
int child[100];//子
int pos[100];//记录字符的坐标
int nexted[100];//排列数组
bool com[100];//判断字符是否出现过
int main()
{
    while(scanf("%s",str)!=EOF){
        memset(com,0,sizeof(com));
        if(str[0]=='#')break;
        int l = strlen(str);
        int len = 0;
        for(int i = 0;i<l;i++){
            int j = i+2;
            com[str[i] - 'A'] = 1;
            while(j<l&&str[j]!=';'){
                com[str[j] - 'A'] = 1;
                root[len] = str[i] - 'A';//实现child[i]' father = root[i]
                child[len++] = str[j] - 'A';
                j++;
            }
            i = j;
        }
        int judge = INF;
        int path[100];//保存结果
        int n = 0;
        for(int i = 0;i<26;i++)
        {
            if(com[i])//根据有没有出现过字符，初始化排列数组
                nexted[n++] = i;
        }
        do{
            int lagest = 0;
            for(int i = 0;i<n;i++)pos[nexted[i]] = i;//记录每个字符在这个排列中的坐标
            for(int i = 0;i<len;i++)
            {
               lagest = max(lagest,abs(pos[child[i]] - pos[root[i]]));
               if(lagest>=judge)break;
            }
            if(lagest<judge){
                judge = lagest;
                memcpy(path,nexted,sizeof(nexted));
            }
        }while(next_permutation(nexted,nexted+n));
        for(int j = 0;j<n;j++)
        {
            if(j==0)
                printf("%c",path[j]+'A');
            else
                printf(" %c",path[j]+'A');
        }
        printf(" -> %dn",judge);

    }
    return 0;
}