这个题，真简单吧。

大概是整张图的边集被划分成若干个边集，我们要选出最小若干个集合，使得剩下的边集组成的图中 $1,n$ 不联通。

显然是最小割，对于集合 $i$ 的边 $(u,v)$，我们连一条 $u\to i\to v$ 的边，表明若选择点 $i$ 割掉，则这条边就走不通了（实际上就是选择集合 $i$）。

显然割不掉点，所以把点拆成入点和出点，然后连 $S\to 1,n\to T$ 的边，除了入点出点边权设为 $1$，其他均设置成 $\infty$。

时间复杂度为 $O(m\sqrt{m})$，复杂度原理参考二分图最大匹配的网络流建模方法。

官方题解。来源：清华大学学生算法协会仓库

题目很明显是一个最小割问题。对于题目描述中的“通知一个分部，在其所有下辖的铁路上设立检查站”操作，我们需要对如下问题进行网络流建模：给定网络流图以及对其边的划分，一次可以以 $1$ 的代价割掉一个划分集合中的所有边。特别地，在同一个划分集合中的所有边都与某个点相邻。

考虑某个形如 $A_i \to x_i \to B_i$ 的划分集合，其中 $A_i$ 和 $B_i$ 为任意点集。考虑如下建模：

• 建立虚点 $p_i, q_i$；
• 有边 $(p_i,q_i,1)$、$(A_i, p_i, 1)$、$(x_i, p_i, 1)$、$(q_i,x_i,1)$、$(q_i,B_i,1)$。

注意到在这个建模中，若所有边都不被割掉，其连通关系恰好为 $A_i \to x \to B_i$，而割掉 $p_i \to q_i$ 之后这个连通关系就消失了，符合我们的需求。

再注意到网络流图上的所有边边权均为 1，直接运行 dinic 算法求解最大流的复杂度为 $O(n \sqrt{m})$，足以通过本题。