P2747 [USACO5.4]周游加拿大Canada Tour

题目描述

你赢得了一场航空公司举办的比赛，奖品是一张加拿大环游机票。旅行在这家航空公司开放的最西边的城市开始，然后一直自西向东旅行，直到你到达最东边的城市，再由东向西返回，直到你回到开始的城市。除了旅行开始的城市之外，每个城市只能访问一次，因为开始的城市必定要被访问两次（在旅行的开始和结束）。

当然不允许使用其他公司的航线或者用其他的交通工具。

给出这个航空公司开放的城市的列表，和两两城市之间的直达航线列表。找出能够访问尽可能多的城市的路线，这条路线必须满足上述条件，也就是从列表中的第一个城市开始旅行，访问到列表中最后一个城市之后再返回第一个城市。

输入输出格式

输入格式：

第 1 行: 航空公司开放的城市数 N 和将要列出的直达航线的数量 V。N 是一个不大于 100 的正整数。V 是任意的正整数。

第 2..N+1 行: 每行包括一个航空公司开放的城市名称。城市名称按照自西向东排列。不会出现两个城市在同一条经线上的情况。每个城市的名称都是一个字符串，最多15字节，由拉丁字母表上的字母组成；城市名称中没有空格。

第 N+2..N+2+V-1 行: 每行包括两个城市名称（由上面列表中的城市名称组成），用一个空格分开。这样就表示两个城市之间的直达双程航线。

输出格式：

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

输入输出样例

输入样例#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

输出样例#1：

说明

题目翻译来自NOCOW。

USACO Training Section 5.4

#include<map>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

map<string,int>ma;

int n,m,tot,ans;

char s[],ss[];

int f[][],dis[][];

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++){

        scanf("%s",s);

        ma[s]=++tot;

    }

    for(int i=;i<=m;i++){

        scanf("%s %s",s,ss);

        dis[ma[ss]][ma[s]]=dis[ma[s]][ma[ss]]=;

    }

    f[][]=;

    for(int i=;i<n;i++)

        for(int j=i+;j<=n;j++)

            for(int k=;k<j;k++)

                if(dis[j][k]&&f[i][k]&&f[i][k]+>f[i][j])

                    f[i][j]=f[j][i]=f[i][k]+;

    ans=;

    for(int i=;i<=n;i++)

        if(dis[i][n])

            ans=max(ans,f[i][n]);

    cout<<ans;

}

巴特西

洛谷 P2747 [USACO5.4]周游加拿大Canada Tour

P2747 [USACO5.4]周游加拿大Canada Tour

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章