题面：周游加拿大Canada Tour

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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

1
7

提示

题目翻译来自NOCOW。

USACO Training Section 5.4

思路

好吧想了半天的题竟然是模板题？！

洛谷题解区说这是 Floyd 求最大环。好吧晦涩难懂，其实按照题目原本的意思就已经很好理解了，就是走一条路 $1\rightarrow n$ 然后找一个路径上没有重复点的路径 $n\rightarrow 1$ 走回去。

好难搞……

但是，如果反过来，找到两条除了起点和终点以外都不含有重复点的路径，是不是略略有点眉目？然后就有了一个很神奇的思路，我们把路径看成两个小人，记录 $dp[i][j]$ 表示小人一走到 $i$ 小人二走到 $j$ 的距离。

这样的递推该怎么递推呢？首先，$dp[i][j]$ 和 $dp[j][i]$ 的值一定是一样的，所以方便递推我们直接设置 $dp[i][j]$ 中 $i < j$ 这样就是可以保证不重复的就可以。

然后就是开始递推，这个真的不难想，不过注意合法状态的情况。

1
2
3
4
5
6
7
8
for(int i=1;i<=n;++i) {
    for(int j=i+1;j<=n;++j)
    {
        for(int k=1;k<j;++k)
            if(g[j][k])
                f[i][j]=f[j][i]=max(f[i][j],f[i][k]+1);
    }
}

最后答案就是找到所有通向 $n$ 的节点，找到 $dp[i][n]$ 的最大值就可以了，为什么不是 $dp[n][n]$ 呢？这样似乎听上去更加符合题目意思，但是注意，我们递推的时候，严格定义了在 $dp[i][j]$ 中 $i \lt j$ ，所以说我们是算不出来 $dp[n][n]$ 的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define MAX 200
map<string,int> M;
int n,m;
bool g[MAX][MAX];
string Pla[MAX],s1,s2;
int f[MAX][MAX],ans=1;
int main()
{
    std::ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>Pla[i];
        M[Pla[i]]=i;
    }
    for(int i=1;i<=m;++i)
    {
        cin>>s1>>s2;
        g[M[s1]][M[s2]]=g[M[s2]][M[s1]]=1;
    }
    memset(f,-63,sizeof(f));
    f[1][1]=1;
    for(int i=1;i<=n;++i)
        for(int j=i+1;j<=n;++j)
        {
            if(i==j)continue;
            for(int k=1;k<j;++k)
                if(g[j][k])
                    f[i][j]=f[j][i]=max(f[i][j],f[i][k]+1);
        }
    for(int i=1;i<=n;++i)
        if(g[i][n])
            ans=max(ans,f[i][n]);
    cout<<ans<<endl;
    return 0;
}