[USACO5.4] 奶牛的电信 Telecowmunication

题目解析

这道题目 P1345 [USACO5.4] 奶牛的电信，核心在于：我们需要破坏最少的点（电脑），让两个特定的点（ $c_1$ 和 $c_2$ ）无法通信。

1. 题目核心分析

🎯 目标

破坏最少的电脑（节点），切断 $c_1$ 到 $c_2$ 的路径。注意：题目明确说 $c_1$ 和 $c_2$ 这两台电脑不能被破坏。

💡 难点：点割 vs 边割

通常的网络流最小割模型（Max-Flow Min-Cut）是用来计算最小割边的（切断边的权值和最小）。但这里要求切断的是点。

🔑 破局关键：拆点法 (Vertex Splitting)

我们需要把“点的限制”转化为“边的限制”。怎么做呢？我们可以把一个点裂变成两个点，中间连一条边。如果我们要“破坏这个点”，在图论模型中就等价于“切断这个点内部的这条边”。

2. 图解：拆点法构建网络

假设有一个节点 $u$ 。

我们要把它拆成 入点 ( $u_{in}$ ) 和 出点 ( $u_{out}$ )。
在这两点之间连一条有向边： $u_{in} \to u_{out}$ 。
这条边的**容量（Capacity）**就是破坏这个点的代价。

构建规则

我们需要构建一个新的流网络，跑最大流（Max Flow）。根据最大流最小割定理，最大流量 = 最小割容量。

点内部的连边 (Node Edge)：
- 对于每一个节点 $i$ ( $1 \le i \le N$ )，将其拆为 $i$ (入点) 和 $i+N$ (出点)。
- 普通电脑：连接 $i \to i+N$ ，容量为 1。（表示破坏它只需要移除1台电脑）。
- 起止电脑 ( $c_1, c_2$ )：题目说不能破坏。连接 $c_1 \to c_1+N$ 和 $c_2 \to c_2+N$ ，容量为 INF（无穷大，表示这条边永远切不断）。
原本的连线 (Wire Edge)：
- 原图中如果有边 $(u, v)$ ，表示线路。线路是不会坏的，只有电脑会坏。
- 所以线路的容量也是 INF。
- 但在拆点后的图中，信号是从一个电脑的“输出”传到另一个电脑的“输入”。
- 连接 $u_{out} \to v_{in}$ ，即 $(u+N) \to v$ ，容量 INF。
- 连接 $v_{out} \to u_{in}$ ，即 $(v+N) \to u$ ，容量 INF。
源点与汇点：
- 源点 (S)： $c_1$ 的入点（或者 $c_1$ 的出点也可以，因为中间边是 INF）。通常取 $c_1$ (即 $c_1$ 的入点)。
- 汇点 (T)： $c_2$ 的出点 (即 $c_2+N$ )。这意味着流必须完整走过 $c_2$ 这台机器。

Mermaid 图示

假设原图是 1 -- 3 -- 2，我们要切断 1 和 2，3 是中间节点。 $N=3$ ，拆点后变成 6 个点。

graph LR
    subgraph Computer_1
    1_in((1入)) == INF ==> 1_out((1出))
    end
  
    subgraph Computer_3
    3_in((3入)) -- 1 --> 3_out((3出))
    end
  
    subgraph Computer_2
    2_in((2入)) == INF ==> 2_out((2出))
    end

    %% 原图的连接变成了出点连入点
    1_out == INF ==> 3_in
    3_out == INF ==> 2_in
  
    %% 反向连接（因为原图是双向的）
    2_out -.-> 3_in
    3_out -.-> 1_in
  
    style 3_in fill:#f9f,stroke:#333
    style 3_out fill:#f9f,stroke:#333
  
    Note[瓶颈在 3入->3出 这条边<br>容量为1, 切断它代表破坏电脑3]

3. 代码实现

我们将使用经典的 Dinic 算法 来求最大流。由于 $N$ 很小 ( $100$ )，Dinic 算法会飞快地跑完。

cpp

/**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * date: 2026-01-17 19:29:00
 */

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5; // 点
const int maxe = 2e6+5; // 边 (注意：要是题目边数的2倍)
const long long INF = 1e10; // 无穷大

int n, m; // 这里的 n 是题目中的电脑数
int c1, c2;
int s, t; // 源点 汇点
int a[maxn];

// 存图的模板
// ... (保留你提供的 linkList 代码，未做修改) ...

//oisnip_begin code/graph/linklist.cpp 内容开始
struct linkList {
    typedef struct {int u,v;long long w;int next;} edge;
    edge e[maxe];
    int h[maxn],edge_cnt=0;
    linkList(){
        reset();
    }

    void reset() {
        edge_cnt=0;
        memset(h,-1,sizeof(h));
    }

    //遍历点u 周围点
    template<typename U>
    void for_each(int u,U func){
        for(int i = h[u] ; i !=-1;i = e[i].next)
            func(e[i].u,e[i].v,e[i].w); //u v w
    }

    void add(int u,int v,int w=0){
        e[edge_cnt] = {u,v,w,h[u]};
        h[u] = edge_cnt++;
    }
    void add2(int u,int v,int w=0){
        add(u,v,w);
        add(v,u,w);
    }
    //下标访问
    edge& operator[](int i){ return e[i]; }

} e;
//oisnip_end code/graph/linklist.cpp 内容结束


// Dinic算法最大流模板 - 基于linkList存图
// ... (保留你提供的 Dinic 代码，未做修改) ...
struct Dinic {
    vector<int> level, cur;  
    int n;  
    
    void init(int n) {
        e.edge_cnt = 0;
        memset(e.h, -1, sizeof(e.h));
        level.resize(n+5);
        cur.resize(n+5);
        this->n = n;
    }
    
    void addEdge(int u, int v, long long cap) { // 修改cap类型为long long适配INF
        e.add(u, v, cap);    
        e.add(v, u, 0);      
    }
    
    bool bfs(int s, int t) {
        fill(level.begin(), level.end(), -1);
        queue<int> q;
        level[s] = 0;
        q.push(s);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for(int i = e.h[u] ; ~i ;i = e[i].next) {
                int v = e[i].v;
                long long cap = e[i].w; // 注意类型
                if (cap > 0 && level[v] < 0) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] >= 0;
    }
    
    long long dfs(int u, int t, long long preFlow) {
        if (u == t || preFlow == 0) return preFlow;
        long long flow = 0;
        
        for (int& cid = cur[u]; cid != -1; cid = e[cid].next) {
            auto& edge = e[cid]; 
            int to = edge.v;
            long long cap = edge.w;
            
            if (level[u] + 1 != level[to] || cap <= 0) continue;
            
            long long tr = dfs(to, t, min(preFlow, cap));

            e[cid].w -= tr ;     
            e[cid ^ 1].w += tr; 
            flow += tr;
            preFlow -= tr;
            if (preFlow == 0) break;
        }
        if (flow == 0) level[u] = -1;
        return flow;
    }
    
    long long maxFlow(int s, int t) {
        long long flow = 0;
        while (bfs(s, t)) {  
            for (int i = 0; i <= n; i++) {
                cur[i] = e.h[i];  
            }
            flow += dfs(s, t, INF);
        }
        return flow;
    }
} dinic;

// --- 上面是模板，下面是针对本题的逻辑实现 ---

void init(){
    // 读取输入: N个电脑, M条连接, C1和C2是需要阻断的两台电脑
    std::cin >> n >> m >> c1 >> c2;

    // 拆点逻辑：
    // 每个点 i 拆分为：入点 i， 出点 i + n
    // 最大节点编号变为 2 * n
    // Dinic 初始化需要覆盖到所有节点
    dinic.init(2 * n + 5);
    
    // 1. 构建点内部的边 (拆点)
    for (int i = 1; i <= n; i++) {
        int u_in = i;
        int u_out = i + n;
        
        long long cap = 1; // 默认破坏一个电脑的代价是 1
        
        // 题目要求：c1 和 c2 不能被破坏
        if (i == c1 || i == c2) {
            cap = INF;
        }
        
        // 添加入点到出点的边
        dinic.addEdge(u_in, u_out, cap);
    }

    // 2. 构建原来的连接 (线路)
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        
        // 线路是无向的，且线路不会坏（容量INF）
        // 信号流向：u出 -> v入， v出 -> u入
        dinic.addEdge(u + n, v, INF);
        dinic.addEdge(v + n, u, INF);
    }

    // 设置源点和汇点
    // 源点：C1 的入点 (C1 本身)
    // 汇点：C2 的出点 (C2 + N)
    s = c1;
    t = c2 + n;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    init(); // 建图
    
    // 跑最大流得到最小割
    cout << dinic.maxFlow(s, t) << "\n";
    
    return 0;
}

4. 易错点与细节

节点编号：
- 因为要拆点，数组大小记得开 $2N$ 以上。
- u 对应的出点是 u + N。如果你的节点编号是从 0 开始的，那就是 u + N；如果是从 1 开始的（本题），依然是 u + N，只要保证不冲突即可。
源点和汇点：
- 最大流的源点是 $c_1$ (入点)，汇点是 $c_2+N$ (出点)。
- 如果写成 dinic(C1, C2)，虽然大多数情况也能跑通（因为中间边是 INF），但逻辑上不严谨，应该涵盖整个流的路径。
INF 的设置：
- $c_1, c_2$ 内部边权是 INF（因为不能被破坏）。
- 电脑之间的连线边权是 INF（因为只能破坏电脑，不能剪断网线）。
- 只有普通电脑内部边权是 1。
无向图处理：
- 题目给的是无向连接。在拆点后的图中，这意味着 $u \to v$ 和 $v \to u$ 都要建边。