5.4.2 Canada Tour 周游加拿大

5.4.2 Canada Tour 周游加拿大

时间: 1ms        内存:64M

描述:

你赢得了一场航空公司举办的比赛,奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始,然后一直自西向东旅行,直到你到达最东边的城市,再由东向西返回,直到你回到开始的城市。每个城市只能访问一次,除了旅行开始的城市之外,这个城市必定要被访问两次(在旅行的开始和结束)。你不允许使用其他公司的航线或者用其他的交通工具。 给出这个航空公司开放的城市的列表,和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线,这条路线必须满足上述条件,也就是从列表中的第一个城市开始旅行,访问到列表中最后一个城市之后再返回第一个城市。

输入:

Line 1: 航空公司开放的城市数 N 和将要列出的直达航线的数量 V。N 是一个不大于 100 的正整数。V 是任意的正整数。 Lines 2..N+1: 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都是一个字符串,最多15字节,由拉丁字母表上的字母和数字组成;城市名称中没有空格。 Lines N+2..N+2+V-1: 每行包括两个城市名称(由上面列表中的城市名称组成),用一个空格分开。这样就表示两个城市之间的直达双程航线。

输出:

Line 1: 按照最佳路线访问的不同城市的数量 M。如果无法找到路线,输出 1。

示例输入:

8 9	
Vancouver		
Yellowknife	
Edmonton
Calgary
Winnipeg
Toronto	
Montreal
Halifax	
Vancouver Edmonton
Vancouver Calgary	
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

示例输出:

7

提示:

参考答案(内存最优[1328]):

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

#define BRANCHNUM 75//声明字典树每个节点的next指针数
#define N 110
#define MAX 100000000

typedef struct Trie_node
{ 
    int num;//记录该城市的编号
    Trie_node *next[BRANCHNUM];//指向各个子树的指针,下表0-25代表26个小写字母,26-52代表26个大写字母
    Trie_node() : num(0)
    {
        memset(next, NULL, sizeof(next));//初始化num和next指针数组
    }
}Trie_Node,*pTrie_Node;

pTrie_Node root;
int n,v;
bool map[N][N];
int dp[N][N];
int res = 1;

void Init()
{ 
    root = new Trie_Node;
} 

void insert(const char* word, int i)
{ 
    pTrie_Node location = root;
    while(*word)
    {//字符串没有结束
        if(location->next[*word-'0'] == NULL)
        {//不存在则建立
            pTrie_Node tmp = new Trie_node();
            location->next[*word-'0'] = tmp;
        }
        location = location->next[*word-'0'];//每插入一步,相当于有一个新串经过,指针要向下移动
        word++;
    } 
    location->num = i;//到达尾部,标记一个串
}

int search(const char *word)
{ 
    pTrie_Node location = root;
    while(*word && location)
    {//没有到字符串尾且没有到Trie树的叶子节点
        location = location->next[*word-'0'];
        word++;
    } 
    if(location != NULL && location->num != 0)
    {//没有到叶子节点且找到了
        return location->num;
    } 
    return 0; 
} 

int main()
{
    Init();
    cin >> n >> v;
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        insert(str.c_str(), i);
    }
    for (int i = 0; i < v; i++)
    {
        string str1, str2;
        cin >> str1 >> str2;
        int c1,c2;
        c1 = search(str1.c_str());
        c2 = search(str2.c_str());
        map[c1][c2] = true;
        map[c2][c1] = true;
    }
    dp[1][1] = 1;//只走过一个城市
    for (int i = 1; i <= n; i++)
    {
        for (int j = i+1;j <= n; j++)
        {
            dp[i][j] = -MAX;
            for (int k = 1; k < j; k++)
            {
                if (map[k][j] == true && dp[i][k] > 0 && dp[i][k] > dp[i][j])
                {//如果从k到j有航线且从i到k经过的城市大于0(dp[i][k]大于0说明存在从i到看的走法)
                    dp[i][j] = dp[i][k]; //取所有满足条件的最大的一个
                }
            }
            dp[j][i] = ++dp[i][j];
        }
    }
    for (int i = 1; i < n; i++)
    {//必须走到终点,所以是dp[i][n]中最大的一个
        if (map[i][n] && dp[i][n] > res)
        {
            res = dp[i][n];
        }
    }
    cout << res << endl;
    return 0; 
}

参考答案(时间最优[8]):

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

#define BRANCHNUM 75//声明字典树每个节点的next指针数
#define N 110
#define MAX 100000000

typedef struct Trie_node
{ 
    int num;//记录该城市的编号
    Trie_node *next[BRANCHNUM];//指向各个子树的指针,下表0-25代表26个小写字母,26-52代表26个大写字母
    Trie_node() : num(0)
    {
        memset(next, NULL, sizeof(next));//初始化num和next指针数组
    }
}Trie_Node,*pTrie_Node;

pTrie_Node root;
int n,v;
bool map[N][N];
int dp[N][N];
int res = 1;

void Init()
{ 
    root = new Trie_Node;
} 

void insert(const char* word, int i)
{ 
    pTrie_Node location = root;
    while(*word)
    {//字符串没有结束
        if(location->next[*word-'0'] == NULL)
        {//不存在则建立
            pTrie_Node tmp = new Trie_node();
            location->next[*word-'0'] = tmp;
        }
        location = location->next[*word-'0'];//每插入一步,相当于有一个新串经过,指针要向下移动
        word++;
    } 
    location->num = i;//到达尾部,标记一个串
}

int search(const char *word)
{ 
    pTrie_Node location = root;
    while(*word && location)
    {//没有到字符串尾且没有到Trie树的叶子节点
        location = location->next[*word-'0'];
        word++;
    } 
    if(location != NULL && location->num != 0)
    {//没有到叶子节点且找到了
        return location->num;
    } 
    return 0; 
} 

int main()
{
    Init();
    cin >> n >> v;
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        insert(str.c_str(), i);
    }
    for (int i = 0; i < v; i++)
    {
        string str1, str2;
        cin >> str1 >> str2;
        int c1,c2;
        c1 = search(str1.c_str());
        c2 = search(str2.c_str());
        map[c1][c2] = true;
        map[c2][c1] = true;
    }
    dp[1][1] = 1;//只走过一个城市
    for (int i = 1; i <= n; i++)
    {
        for (int j = i+1;j <= n; j++)
        {
            dp[i][j] = -MAX;
            for (int k = 1; k < j; k++)
            {
                if (map[k][j] == true && dp[i][k] > 0 && dp[i][k] > dp[i][j])
                {//如果从k到j有航线且从i到k经过的城市大于0(dp[i][k]大于0说明存在从i到看的走法)
                    dp[i][j] = dp[i][k]; //取所有满足条件的最大的一个
                }
            }
            dp[j][i] = ++dp[i][j];
        }
    }
    for (int i = 1; i < n; i++)
    {//必须走到终点,所以是dp[i][n]中最大的一个
        if (map[i][n] && dp[i][n] > res)
        {
            res = dp[i][n];
        }
    }
    cout << res << endl;
    return 0; 
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注