题目分析

JYY 需要观看 RPG 游戏中的所有支线剧情。游戏有 $N$ 个剧情点，从每个剧情点可以前往多个其他剧情点，每条支线剧情需要一定观看时间。JYY 从 1 号剧情点开始，可以随时退出游戏重新开始。目标是找到观看所有支线剧情的最小总时间。

解题思路

核心思想

将问题建模为有上下界的最小费用流问题：

• 每个剧情点作为网络中的节点
• 每条支线剧情作为容量下界为 1 的边（必须观看一次）
• 边的费用为观看该剧情所需时间
• 重新开始游戏通过循环流来建模

关键技术

1. 网络流建模：将剧情观看转化为流问题
2. 上下界处理：使用辅助源汇点处理流量平衡
3. 最小费用流：SPFA 算法寻找最小费用增广路

算法步骤

1. 构建基础图：剧情点作为节点，支线剧情作为边
2. 处理上下界：构建辅助图满足流量约束
3. 计算最小费用流：反复增广直到找到最优解
4. 输出总费用：即最小总观看时间

完整代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 5;
const int INF = 1e9;

// 边结构体
struct Edge {
    int to, next, capacity, cost;
};

Edge edges[N];
int head[N], total_edges = 1;
int balance_flow[N];  // 节点的流量平衡值
int max_cost = 0;     // 总费用
int source, sink, super_source, super_sink;
int n;

// 距离、增量、队列标记、前驱边
int dist[N], increment[N], in_queue[N], previous_edge[N];

// 添加边函数
void add_edge(int from, int to, int lower_bound, int upper_bound, int cost) {
    // 处理流量平衡
    balance_flow[from] -= lower_bound;
    balance_flow[to] += lower_bound;
    max_cost += lower_bound * cost;
    
    // 添加正向边
    edges[++total_edges] = {to, head[from], upper_bound - lower_bound, cost};
    head[from] = total_edges;
    
    // 添加反向边
    edges[++total_edges] = {from, head[to], 0, -cost};
    head[to] = total_edges;
}

// SPFA 寻找最小费用增广路
bool find_augmenting_path(int start, int end) {
    for (int i = 1; i <= super_sink; i++) {
        dist[i] = INF;
        in_queue[i] = 0;
    }
    
    queue<int> q;
    increment[start] = INF;
    dist[start] = 0;
    q.push(start);
    in_queue[start] = 1;
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        in_queue[current] = 0;
        
        for (int i = head[current]; i; i = edges[i].next) {
            if (edges[i].capacity > 0 && dist[current] + edges[i].cost < dist[edges[i].to]) {
                dist[edges[i].to] = dist[current] + edges[i].cost;
                increment[edges[i].to] = min(increment[current], edges[i].capacity);
                previous_edge[edges[i].to] = i;
                
                if (!in_queue[edges[i].to]) {
                    in_queue[edges[i].to] = 1;
                    q.push(edges[i].to);
                }
            }
        }
    }
    
    return dist[end] < INF;
}

// 沿增广路更新流量
void update_flow(int start, int end) {
    for (int i = end; i != start; i = edges[previous_edge[i] ^ 1].to) {
        edges[previous_edge[i]].capacity -= increment[end];
        edges[previous_edge[i] ^ 1].capacity += increment[end];
    }
    max_cost += dist[end] * increment[end];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    
    // 设置节点编号
    source = 1;                    // 源点：1号剧情点
    sink = n + 1;                  // 汇点
    super_source = sink + 1;       // 辅助源点
    super_sink = super_source + 1; // 辅助汇点
    
    // 读入支线剧情并建图
    for (int i = 1; i <= n; i++) {
        int branch_count;
        cin >> branch_count;
        
        for (int j = 0; j < branch_count; j++) {
            int target, time;
            cin >> target >> time;
            // 添加支线剧情边：下界1，上界很大，费用为观看时间
            add_edge(i, target, 1, INF, time);
        }
        
        // 连接到汇点的边，允许在任何剧情点结束
        add_edge(i, sink, 0, INF, 0);
    }
    
    // 处理上下界约束
    for (int i = 1; i <= n; i++) {
        if (balance_flow[i] > 0) {
            // 需要流入的节点连接到辅助源点
            add_edge(super_source, i, 0, balance_flow[i], 0);
        } else if (balance_flow[i] < 0) {
            // 需要流出的节点连接到辅助汇点
            add_edge(i, super_sink, 0, -balance_flow[i], 0);
        }
    }
    
    // 添加从汇点到源点的边，形成循环流（允许重新开始游戏）
    add_edge(sink, source, 0, INF, 0);
    
    // 计算最小费用流
    while (find_augmenting_path(super_source, super_sink)) {
        update_flow(super_source, super_sink);
    }
    
    // 输出最小总时间
    cout << max_cost << endl;
    
    return 0;
}

代码说明

关键数据结构

• Edge 结构体：存储边的终点、容量、费用等信息
• balance_flow 数组：处理节点的流量平衡约束
• dist 数组：存储从源点到各节点的最短距离（费用）
• increment 数组：记录增广路径上的最小残余容量

网络流建模

1. 节点设置：

   • 普通节点：1 到 n，对应剧情点
   • 汇点：n+1
   • 辅助源点：n+2
   • 辅助汇点：n+3

2. 边设置：

   add_edge(i, target, 1, INF, time);
   

   • 下界 1：保证每条支线剧情至少观看一次
   • 上界 INF：允许重复观看（通过重新开始游戏）
   • 费用 time：观看该剧情所需时间

3. 重新开始机制：

   add_edge(sink, source, 0, INF, 0);
   

   允许从游戏结束重新回到开始

算法流程

1. 读入建图：构建基础的网络流图
2. 上下界处理：通过辅助源汇点满足流量平衡
3. 费用流计算：使用 SPFA 反复寻找最小费用增广路
4. 结果输出：总费用即为最小观看时间

复杂度分析

• 时间复杂度：$O(F \cdot (N + E))$，其中 $F$ 是流量，$E$ 是边数
• 空间复杂度：$O(N + E)$ 。