This post is written in Chinese. Please consider using Google Translate

这道题使我费了好大的劲才想出来，没有注意道题中只能自西向东的约定。如果没有这个约定，那就是个哈密尔顿圈问题了，NP难。

题中所说的只能定向旅行，实际上取消了该题的后效性，可以用动态规划来做。把返回的路线反向，假定有两个人分别从起点到终点进行旅行，那么整条路线就变成了两条不相交的从起点到终点的路线。

状态设定 f[i,j] 为假定的甲乙两人，甲走到第i个城市，乙走到第j个城市时，两人走过的城市数目的和。

初始状态 f[1,1]=1

状态转移方程 f[j,i]=f[i,j]=max{f[i,k]+1}(k到j存在飞机航线，1<=k<j) 交换甲乙，则肯定有f[j,i]=f[i,j]。

目标结果 由于题中告知必须走到终点才能返回，输出结果一定是max{f[i,N]}(i到N存在飞机航线)。 如果没有经过城市数目大于1的可行目标状态，则无法完成这次环游，输出1。

这是加拿大IOI93的一道原题。在WC2008中听吴教授说道，当时参加IOI的选手没有人了解动态规划，对这道题束手无策。选手们都用上了最复杂的搜索技巧，有人还写了双向搜索，可是都没有通过。回国后开始研究，最终提出了动态规划这一算法设计方法，于是动态规划变成了之后竞赛出题的热点。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 2892 KB]
   Test 2: TEST OK [0.011 secs, 2892 KB]
   Test 3: TEST OK [0.000 secs, 2888 KB]
   Test 4: TEST OK [0.000 secs, 2888 KB]
   Test 5: TEST OK [0.000 secs, 2888 KB]
   Test 6: TEST OK [0.000 secs, 2888 KB]
   Test 7: TEST OK [0.000 secs, 2888 KB]
   Test 8: TEST OK [0.022 secs, 2892 KB]
   Test 9: TEST OK [0.022 secs, 2892 KB]
   Test 10: TEST OK [0.000 secs, 2888 KB]
   Test 11: TEST OK [0.022 secs, 2892 KB]

All tests OK.

Your program ('tour') produced all correct answers! This is your submission #2 for this problem. Congratulations! 

/*
ID: cmykrgb1
PROG: tour
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <string>
#define MAXN 101
#define INF 0x7FFFFFFF

using namespace std;

ifstream fi("tour.in");
ofstream fo("tour.out");

bool adj[MAXN][MAXN];
int f[MAXN][MAXN];
string City[MAXN];
int N,ans;

inline int getnum(string &s)
{
    for (int i=1;i<=N;i++)
        if (s==City[i])
            return i;
}

void init()
{
    int i,V,d1,d2;
    string C1,C2;
    fi >> N >> V;
    for (i=1;i<=N;i++)
        fi >> City[i];
    for (i=1;i<=V;i++)
    {
        fi >> C1 >> C2;
        adj[d2][d1]=adj[d1=getnum(C1)][d2=getnum(C2)]=true;
    }
}

void dynamic()
{
    int i,j,k;
    f[1][1]=1;
    for (i=1;i<=N;i++)
    {
        for (j=i+1;j<=N;j++)
        {
            f[i][j]=-INF;
            for (k=1;k<j;k++)
            {
                if (adj[k][j] && f[i][k]>0 && f[i][k]>f[i][j])
                    f[i][j]=f[i][k];
            }
            f[j][i]=++f[i][j];
            j=j;
        }
    }
}

void print()
{
    int i;
    ans=1;
    for (i=1;i<N;i++)
        if (adj[i][N] && f[i][N]>ans)
            ans=f[i][N];
    fo << ans << endl;
    fi.close();
    fo.close();
}

int main()
{
    init();
    dynamic();
    print();
    return 0;
}