P1345 奶牛的电信

切断点而非切断边时，把点拆成一条边

问题

P1345 奶牛的电信
给定一张无向通信网络，其中有两台指定电脑不能损坏。每次可以损坏其余一台电脑，并同时删除它连接的所有线路，要求最少损坏多少台电脑才能使两个指定点不再连通。

数据规模：$1\le N\le100$，$1\le M\le600$。

这是一个割的模型，我首先会想到 Tarjan 割点 -- 点双连通分量的模型。但是割点只能回答只删掉这一个点，是否能断掉两个关键点之间的路径。

割点与点双只记录了 “是否存在一个顶点就能切断连通性” 这一层。如果 $S,T$ 落在同一个点双内部，只能知道不存在单个普通顶点把它们分开，也就是最小 $S-T$ 点割至少为 $2$；但点双并不能继续告诉我们最小点割究竟是 $2,3$ 或者是更大的数。

那该怎么解决呢？既然是割相关的问题，不妨试试网络流中的最小割呢？

Menger 定理

对两个指定顶点 $S,T$，$S,T$ 之间内部点不相交路径的最大数量，等于使 $S,T$ 不连通所需删除的最少内部顶点数。

本题直接要求 $S-T$ 最小点割。Menger 定理告诉我们，它同时等于 $S,T$ 之间最大内部点不相交路径数；于是既可以从最小割角度理解，也可以通过点容量最大流计算。

普通最大流限制的是边容量，而本题的限制落在点上，因此把每个普通点拆成 $i_{in}$ 与 $i_{out}$，中间连容量为 $1$ 的边，这里就跟 P1231 教辅的组成 的拆点很像了。从最大流角度看，它保证每个普通点最多被一条内部点不相交路径使用；从最小割角度看，割掉这条边的代价为 $1$，正好表示删除这个顶点。

而原图中的关系边，容量就直接设置为 $+oo$，因为它们不应该成为瓶颈。这样最小割就不会通过低代价地切断原通信边绕过 “只能损坏电脑” 的题意。

最后从指定起点的 $S_{out}$ 到指定终点 $T_{in}$ 求最大流，根据最大流最小割定理，得到的最小割容量就是使两个指定点断开的最少删点数。

▶

P1345 建图

namespace DINIC { /* 模板代码略 */ }
using namespace DINIC;

void solve( ) {
    int n = read( ), m = read( );
    int S = read( ), T = read( );

    vector<int> ci( n + 1 );
    vector<int> co( n + 1 );

    int tot = 0;
    for( int i = 1; i <= n; ++ i ) ci[i] = ++ tot;
    for( int i = 1; i <= n; ++ i ) co[i] = ++ tot;
    init( tot );

    for( int i = 1; i <= m; ++ i ) {
        int u = read( ), v = read( );
        add_edge( co[u], ci[v], inf );
        add_edge( co[v], ci[u], inf );
    }

    for( int i = 1; i <= n; ++ i ) {
        if( i == S || i == T ) add_edge( ci[i], co[i], inf );
        else add_edge( ci[i], co[i], 1 );
    }

    ll mncut = Dinic( co[S], ci[T], tot );
    cout << mncut << '\n';
}