USACO/tour

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 5 .4中的OI题目Canada Tour的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

动态规划

把返回的路线反向，那么整条路线就变成了两条不相交的从起点到终点的路线。这样我们可以用DP解决。

状态设定

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

初始状态

f[1,1]=1

状态转移方程

f[j,i]=f[i,j]=max{f[i,k]+1}(k到j存在飞机航线，以及f[i,k]>0，就是说存在f[i,k]的走法，1<=k<j

交换甲乙，则肯定有f[j,i]=f[i,j]。

目标结果

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

【路人】说个审题的细节：开始一直没注意必须从西向东和从东向西……于是一直没搞明白怎么确定dp的顺序，以为是给了张普通的无向图，于是纠结良久，终于醒悟

 (不理解啊。。能否详细点？）

网络流

【建模方法】

把第i个城市拆分成两个顶点<i.a>,<i.b>。 1、对于每个城市i，连接(<i.a>,<i.b>)一条容量为1，费用为1的有向边，特殊地(<1.a>,<1.b>)和(<N.a>,<N.b>)容量设为2。 2、如果城市i,j(j>i)之间有航线，从<i.b>到<j.a>连接一条容量为1，费用为0的有向边。 求源<1.a>到汇<N.b>的最大费用最大流。 如果(<1.a>,<1.b>)不是满流，那么无解。否则存在解，即为最大费用最大流量 - 2。

【建模分析】

每条航线都是自西向东，本题可以转化为求航线图中从1到N两条不相交的路径，使得路径长度之和最大。转化为网络流模型，就是找两条最长的增广路。由于每个城市只能访问一次，要把城市拆成两个点，之间连接一条容量为1的边，费用设为1。因为要找两条路径，所以起始点和终点内部的边容量要设为2。那么费用流值-2就是两条路径长度之和，为什么减2，因为有两条容量为2的边多算了1的费用。求最大费用最大流后，如果(<1.a>,<1.b>)不是满流，那么我们找到的路径不够2条（可能是1条，也可能0条），所以无解。

【可能的简化方法--最大流】

因为这种建图方法的特殊性，我们注意到：一条从源到汇的路上的边费用必然交替是1/0 （因为先经过一条由原节点拆成的边（费用1） 再经过本来原图就有的边（费用0））。那么我们只需要求得最大流减去2再除以2就可以得到答案。样例：（7 + 9）/ 2 = 7 //CD问：首先 （7+9）/2=8<>7 ，其次，根据文主所述，应该最大费用-2才=点数，最大流一直是2，而我们应该求得的是路径长度d，(d-2）/2才=点数。 楼主解释下！//

问题来源

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

↑

The term dynamic programming was originally used in the 1940s by Richard Bellman to describe the process of solving problems where one needs to find the best decisions one after another. By 1953, he refined this to the modern meaning, referring specifically to nesting smaller decision problems inside larger decisions,[2] and the field was thereafter recognized by the IEEE as a systems analysis and engineering topic. Bellman's contribution is remembered in the name of the Bellman equation, a central result of dynamic programming which restates an optimization problem in recursive form.

参考代码

C

C++

Pascal