题解_有向无环图

这是一道经典的有向无环图（$DAG$）路径覆盖问题。由于剧情不可逆（$DAG$），且每次重新开始游戏等价于选择一条从 1 出发的路径，我们需要用若干条路径覆盖所有边，最小化总时间（路径长度之和）。
思路：最小费用最大流
关键观察：每条边必须被恰好经过一次。重新开始游戏意味着路径之间可以"拼接"——如果一条路径在节点$v$结束，另一条可以从$v$开始，这样就能省下重复走前缀的时间。
建模：
1.
拆点：将每个节点$i$拆成入点$i_{in}$ 和出点$i_{out}$，连边$(i_{in} \to i_{out})$，容量$+\infty$，费用$0$。
2.
原图边：对于原图中的每条有向边$(u \to v, w)$，连边$(u_{out} \to v_{in})$，容量 1，费用$w$。
3.
源汇：源点 S 连向$1_{out}$（容量 $+\infty$，费用 0）；所有节点的$i_{in}$连
求最小费用最大流。此时：

每条原图边恰好被流过一次（容量为 1，必须满流才能覆盖所有边）。

节点拆分边允许流量"穿过"节点，实现路径的拼接（即不重新开始游戏）。

总费用就是所有被经过边的权值之和，即最少时间。
答案：求出的最小费用值。

C++代码：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 605; // 拆点后最多 600 个点
const long long INF = 1e18;

struct Edge {
    int to, cap, cost, rev;
};

vector<Edge> G[MAXN];
int dist[MAXN], prevv[MAXN], preve[MAXN];
bool inq[MAXN];

void add_edge(int from, int to, int cap, int cost) {
    G[from].push_back({to, cap, cost, (int)G[to].size()});
    G[to].push_back({from, 0, -cost, (int)G[from].size() - 1});
}

// SPFA 求最短增广路（费用可为正，也可用 Dijkstra+势）
pair<int, long long> min_cost_max_flow(int s, int t) {
    int flow = 0;
    long long cost = 0;
    while (true) {
        fill(dist, dist + MAXN, INT_MAX);
        memset(inq, false, sizeof(inq));
        dist[s] = 0;
        queue<int> q;
        q.push(s);
        inq[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for (int i = 0; i < G[u].size(); i++) {
                Edge &e = G[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    prevv[e.to] = u;
                    preve[e.to] = i;
                    if (!inq[e.to]) {
                        q.push(e.to);
                        inq[e.to] = true;
                    }
                }
            }
        }
        if (dist[t] == INT_MAX) break;
        // 找到增广路，尽可能增广（这里每次增广 1 单位即可，因为原图边容量为 1）
        int d = INT_MAX;
        for (int v = t; v != s; v = prevv[v])
            d = min(d, G[prevv[v]][preve[v]].cap);
        flow += d;
        cost += (long long)d * dist[t];
        for (int v = t; v != s; v = prevv[v]) {
            Edge &e = G[prevv[v]][preve[v]];
            e.cap -= d;
            G[v][e.rev].cap += d;
        }
    }
    return {flow, cost};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    int S = 0, T = 2 * N + 1;
    // 节点 i: 入点 = i, 出点 = i + N (1-indexed)
    // 源点 S=0, 汇点 T=2N+1
    
    // 源点连向 1 的出点
    add_edge(S, 1 + N, INF, 0);
    // 每个节点的入点连向汇点
    for (int i = 1; i <= N; i++) {
        add_edge(i, T, INF, 0);
    }
    
    for (int i = 1; i <= N; i++) {
        int K;
        cin >> K;
        // 拆点边：允许流量穿过节点
        add_edge(i, i + N, INF, 0);
        
        for (int j = 0; j < K; j++) {
            int b, t;
            cin >> b >> t;
            // 原图边：从 i 的出点到 b 的入点
            add_edge(i + N, b, 1, t);
        }
    }
    
    auto res = min_cost_max_flow(S, T);
    cout << res.second << "\n";
    
    return 0;
}