铁路检查站 题解

题目分析

这道题要求选择最少数量的分部，使得这些分部管理的铁路能够覆盖从1号站到n号站的所有路径。

关键点：

• 铁路是单向的
• 每个分部管理若干铁路，且分部办公室位于铁路的某一端
• 需要选择分部集合，使得这些分部的铁路的并集包含所有1→n的路径

解题思路

核心观察

1. 最小割模型：问题可以转化为在分部图中求最小割
2. 分部拆点：将每个分部拆分为入点和出点
3. 网络流建模：通过巧妙的建图将问题转化为最小割问题

算法设计

代码采用了网络流最小割的方法：

主要步骤：

1. 分部拆点：每个分部拆分为两个节点，中间连容量1的边
2. 铁路连接：根据铁路与分部的关系连接相应节点
3. 最小割计算：使用Dinic算法求最小割

代码详解

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 4e5 + 5;
const int inf = 1e18;

int n, m, c, s, t;
int tot = 1, head[N];
int dis[N], cur[N];

struct node {
    int v, w, nxt;
} e[N];

void add(int u, int v, int w) {
    e[++tot] = {v, w, head[u]};
    head[u] = tot;
}

void ins(int u, int v, int w) {
    add(u, v, w), add(v, u, 0);  // 添加双向边，反向边容量0
}

// BFS分层
bool bfs() {
    fill(dis + 1, dis + n + 2 * c + 1, inf);
    queue<int> q;
    q.push(s);
    dis[s] = 0;
    cur[s] = head[s];
    
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = head[u]; i; i = e[i].nxt) {
            int v = e[i].v;
            if (e[i].w > 0 && dis[v] == inf) {
                q.push(v);
                cur[v] = head[v];
                dis[v] = dis[u] + 1;
                if (v == t) return true;
            }
        }
    }
    return false;
}

// DFS增广
int dfs(int u, int sum) {
    if (u == t) return sum;
    int res = 0;
    for (int i = cur[u]; i && sum; i = e[i].nxt) {
        int v = e[i].v;
        cur[u] = i;
        if (e[i].w > 0 && dis[v] == dis[u] + 1) {
            int k = dfs(v, min(e[i].w, sum));
            if (k == 0) dis[v] = inf;
            e[i].w -= k;
            e[i ^ 1].w += k;
            sum -= k;
            res += k;
        }
    }
    return res;
}

// Dinic算法求最大流
int dinic() {
    int ans = 0;
    while (bfs()) 
        ans += dfs(s, inf);
    return ans;
}

int p[N];  // 分部所在车站

signed main() {
    cin >> n >> m >> c;
    
    // 读入分部位置
    for (int i = 1; i <= c; i++) 
        cin >> p[i];
    
    // 分部拆点：每个分部拆为入点(n+i)和出点(n+c+i)
    for (int i = 1; i <= c; i++) {
        ins(p[i], n + i, inf);        // 车站 -> 分部入点
        ins(n + c + i, p[i], inf);    // 分部出点 -> 车站
        ins(n + i, n + i + c, 1);     // 分部入点 -> 分部出点，容量1
    }
    
    // 处理铁路
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        
        if (u == v) continue;  // 自环忽略
        
        if (p[w] == u) 
            ins(n + w + c, v, inf);  // 分部w出点 -> 终点v
        else if (p[w] == v) 
            ins(u, n + w, inf);      // 起点u -> 分部w入点
    }
    
    s = 1, t = n;  // 源点为1，汇点为n
    cout << dinic() << endl;
    return 0;
}

算法原理详解

1. 网络流建模

将问题转化为最小割问题：

• 源点：车站1
• 汇点：车站n
• 分部节点：每个分部拆分为入点和出点，中间连容量1的边

2. 分部拆点意义

对于分部i：

• 节点 n+i：分部入点
• 节点 n+c+i：分部出点
• 边 (n+i, n+c+i)：容量1，表示选择该分部的代价

3. 铁路连接规则

对于铁路(u, v, w)：

• 如果分部w在u：分部w出点 → v
• 如果分部w在v：u → 分部w入点

这样建模后，从1到n的路径必须经过某些分部，选择分部相当于在图中做割。

4. 最小割与答案

最小割的值就是需要选择的最少分部数量，因为：

• 每条从1到n的路径都被割断
• 割边对应选择的分部
• 容量1表示每个分部代价为1

复杂度分析

• 时间复杂度：O((n+c+m)²) Dinic算法复杂度
• 空间复杂度：O(n+c+m) 存储图结构

样例解析

对于样例：

5 10 3
3 1 4  # 分部1在站3，分部2在站1，分部3在站4
... (铁路数据)

建图：

• 分部1：站3 → 分部1入 → 分部1出 → 站3
• 分部2：站1 → 分部2入 → 分部2出 → 站1
• 分部3：站4 → 分部3入 → 分部3出 → 站4

铁路连接根据分部位置建立相应边。

最小割为2，表示需要选择2个分部。

关键技巧

1. 分部拆点：将选择代价转化为边容量
2. 无限容量边：保证路径必须经过分部节点
3. Dinic算法：高效求解最大流/最小割
4. 反向边：支持增广路径查找

总结

这道题的解题亮点：

1. 问题转化：将覆盖问题转化为最小割问题
2. 巧妙建图：通过分部拆点建模选择代价
3. 高效算法：使用Dinic算法求解
4. 完整性：处理了大规模数据情况

算法通过深入的问题分析和巧妙的网络流建模，将复杂的路径覆盖问题转化为标准的最小割问题，展示了图论建模的强大能力。