1 4 7 10 112 5 83 6 93

Solution

1.模型：有向无环图DAG的最小路径覆盖

• s->Xi，容量为1。
• Xi->Yj，(i, j)∈E，容量上界为1。
• Yi->t，容量上界为1。

DAG的最小路径覆盖=|V|-对应二分图的最大匹配。

约束是什么？对路径的定义中，有至关重要的一点：允许长度为0。于是解的存在性得到了保证。因此，只需满足：对于任意一点，至多有一条与它关联的入边和与它关联的出边被选中。
二分图的匹配，可以从顶点对应的角度看待，也可以从边的角度看待：选出一些边，使得每个顶点至多与一条边关联。和本问题的约束对比，发现有向无环图不是二分图，并且对于顶点而言，边分为入边和出边两类。考虑把点i拆成Xi、Yi，入边连到Yi，出边从Xi出发。这样，问题的约束便和二分图匹配相一致。
目标是什么？使路径覆盖数最小。除了直接数，还能用什么来刻画路径覆盖数？头的数量或尾的数量。什么样的点是头？没有匹配边与对应的Yi关联。尾？没有匹配边与对应的Xi关联。所以，DAG的最小路径覆盖=|V|-对应二分图的最大匹配。

hzwer这儿有另一种更简洁的看待方法：

如果无匹配，显然要n条路径才能覆盖所有点，两个点匹配意味着将可以把它们用一条路径覆盖，路径数就可以减1

我还有一种另类看待方法：
带上下界的网络流。
Step 1
- s->Xi，容量上界为1。
- Xi->Yi，容量下界为1，上界inf。
- Yi->Xj，(i, j)∈E，容量上界为1。
- Yi->t，容量上界为1。
求解s-t最小流。

Step 2
看出一个可行流，于是省去通常求解s-t可行流的步骤。
网络变换为：
- Xi->s，容量上界为1。
- Yi->Xj，(i, j)∈E，容量上界为1。
- t->Yi，容量上界为1。
此网络的t-s最大流与原s-t可行流的叠加，即为原s-t最小流。s-t可行流的值为|V|，用|V|去减t-s最大流即可。

这种看待方法和hzwer的在实质上相同，但是是从形式上的变换得到的。

为什么强调DAG？因为我们只是简单地拆点、匹配，而没有在意这两点是否已经在同一条路径里了。比如，一个环，对应二分图的最大匹配为|V|，实际上，作为一条有始有终的“路径”，它是不能封口的。

转载自http://blog.csdn.net/ruoruo_cheng

因此，ans=n-最大匹配

2.算法

二分图最大匹配用网络流最大流实现