---

一、题意理解

1. 基本模型

• 有 $N$ 个城市，按从西向东顺序给出编号 $1$ 到 $N$。
• 起点是 $1$ 号（最西端），终点是 $N$ 号（最东端）。
• 有 $V$ 条双向航线（无向边），航线连接两个城市。
• 要求一条旅行路线：
  1. 从 $1$ 出发，经过一些城市到 $N$（向东走）。
  2. 再从 $N$ 出发，经过另一些城市回到 $1$（向西走）。
  3. 除起点 $1$ 外，每个城市只能访问一次。
  4. 目标：使访问的不同城市总数最多（不包括起点 $1$ 的重复访问）。

2. 等价转化

由于除起点外每个城市只能访问一次，而路线分为“去程”和“回程”，这相当于从 $1$ 到 $N$ 的两条不相交（除起点和终点）的路径。

但注意：起点 $1$ 在去程和回程各访问一次，所以 $1$ 会被访问两次；终点 $N$ 也是两次。

问题等价于：找到两条从 $1$ 到 $N$ 的**顶点不相交（除起点和终点）**的路径，使得经过的不同城市数最多。

---

二、建模为网络流

这是经典的顶点不相交路径问题，可以通过拆点转化为边不相交路径问题。

1. 拆点

对于每个城市 $i$，拆成两个点：入点 $i$ 和出点 $i'$（代码中出点是 $i+n$），连接一条边 $(i, i')$：

• 容量 = 1（保证该城市只能被访问一次）
• 费用 = -1（因为我们希望最大化经过的城市数，所以在费用流中设负费用，最小化总费用就是最大化城市数）

例外：

• 起点 $1$：容量 = 2（因为起点在去程和回程各用一次）
• 终点 $N$：容量 = 2（同理）

2. 航线边

对于原图中的航线 $(A,B)$（假设 $A < B$ 保证从西向东或平等），我们添加边 $(A', B)$，容量 = 1，费用 = 0。

为什么是 $A' \to B$？
因为从 $A$ 到 $B$ 需要经过 $A$ 的出点（即 $A'$）到 $B$ 的入点（即 $B$），这样保证流量经过 $A$ 的拆点边。

由于航线是双向的，但题目要求去程从西向东，回程从东向西，所以我们需要保证从西向东的边（$A<B$）和从东向西的边（$B<A$）都要考虑？
实际上，回程时路径是反向的，但我们的图是有向图，所以对于航线 $(A,B)$，当 $A<B$ 时，我们可以从 $A$ 到 $B$（向东），也可以从 $B$ 到 $A$（向西）。
但代码中只添加了 $A' \to B$（$A<B$），这只允许向东的移动。为什么可行？
因为两条路径中，一条是 $1 \to N$（向东），另一条是 $N \to 1$（反向），但我们可以将反向路径看作另一条从 $1$ 到 $N$ 的路径（在网络流中，流量从 $1$ 流向 $N$，两条路径都是正向的）。
这样，所有边都是 $A' \to B$（$A<B$），流量只能从编号小的流向编号大的，保证了两条路径都是严格从西向东的。

关键：这样建模后，两条从 $1$ 到 $N$ 的路径，其中一条对应实际的去程，另一条对应回程的反向，最终输出时再反向回来。

---

3. 特殊处理直接边 $(1,N)$

如果存在航线 $(1,N)$，可以直接从起点飞到终点，那么在去程和回程可能直接使用这条边。
代码中特别处理：

if (A == 1 && B == n) {
    addEdge(A + n, B, 1, 0);
}

这里容量设为 1，因为两条路径中最多有一条可以直接飞 $(1,N)$？
但下面还有 addEdge(A + n, B, 1, 0)，所以这条边实际上容量 1，但添加了两次？看起来有误，但实际可能是因为要允许两条路径都可以使用这条边？
其实应该容量为 2，因为去程和回程都可能使用这条边。

---

4. 网络流模型总结

• 源点 $S = 1$，汇点 $T = N'$（即 $N+n$）。
• 对每个 $i$：$i \to i'$，容量 = 1（$i=1$ 或 $N$ 时为 2），费用 = -1。
• 对每条航线 $(A,B)$（$A<B$）：$A' \to B$，容量 = 1，费用 = 0。
• 求从 $S$ 到 $T$ 的最大流，并且因为费用为负，求最小费用（即最大城市数）。

最大流如果等于 2，说明找到两条不相交路径，最小费用 = -（总城市数）。

---

三、算法步骤

1. 读入城市，建立字符串到编号的映射。
2. 建图：
   • 拆点边：$i \to i+n$，容量 = 1（$i=1,N$ 为 2），费用 = -1。
   • 航线边：$A+n \to B$，容量 = 1，费用 = 0（保证 $A<B$）。
3. 跑最小费用最大流（实际是最大费用，因为费用为负，最小化总负费用 = 最大化城市数）。
4. 如果最大流 $<2$，输出 No Solution!。
5. 否则，根据流量残量图找到两条路径，输出路线。

---

四、输出路径

1. 路径恢复

在费用流中，每条流的实际路径可以通过流量残量来追踪。
代码中记录了 flowto[now] 表示从 $now$ 流出流量到达的点。

由于我们建图时所有边都是从小编号到大编号（$A<B$），所以两条从 $1$ 到 $N$ 的路径都是递增的。

2. 找两条路径

从起点 $1$ 出发，沿残量网络找两条到 $N$ 的路径。
因为起点容量为 2，所以有两条流出去。

代码中的查找：

for (i = 2; i <= n; i++) {
    for (j = head[i]; j; j = xian[j].next) {
        to = xian[j].to;
        if (to == 1 + n && xian[j].flow) {
            dfs2(i);
            flag = i;
            break;
        }
    }
    if (flag) break;
}

这里找的是第一条路径：从某个城市 $i$（$i>1$）有流量流回 $1'$（即 $1+n$）？
实际上这里找的是回程路径（反向），因为 $to == 1+n$ 表示从 $i$ 有边到 $1'$，这对应回程时从 $i$ 到 $1$。

dfs2(i) 输出从 $i$ 到 $N$ 的路径（反向打印，即实际是回程路径从 $N$ 到 $i$ 的部分）。

然后找第二条路径（去程路径），dfs(i) 输出从 $i$ 到 $N$ 的路径（正向）。

---

3. 输出顺序

最终输出：

1. 总城市数 = $-mincost$。
2. 起点 $1$。
3. 第一条路径（去程）：从 $1$ 到 $N$ 经过的城市。
4. 第二条路径（回程的反向）：从 $N$ 到 $1$ 经过的城市（不包含 $1$）。
5. 最后再输出起点 $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: Vancouver
2: Yellowknife
3: Edmonton
4: Calgary
5: Winnipeg
6: Toronto
7: Montreal
8: Halifax

建图后，最大流 = 2，最小费用 = -7，总访问城市数 7。

输出路线：

7
Vancouver (1)
Edmonton (3)
Montreal (7)
Halifax (8)
Toronto (6)
Winnipeg (5)
Calgary (4)
Vancouver (1)

这是两条路径：

• 去程：1 → 3 → 7 → 8
• 回程：8 → 6 → 5 → 4 → 1

---

六、总结

1. 拆点：解决顶点访问次数限制。
2. 费用流：最大化经过的城市数（负费用）。
3. 边方向：只建 $A<B$ 的边，保证流量从西向东，两条路径分别对应去程和回程的反向。
4. 路径恢复：根据残量流量输出路线。

这个解法将顶点不相交路径问题转化为网络流，是解决此类问题的经典方法。