题目链接：LOJ 2226

宅男 JYY 非常喜欢玩 RPG 游戏，比如仙剑，轩辕剑等等。不过 JYY 喜欢的并不是战斗场景，而是类似电视剧一般的充满恩怨情仇的剧情。这些游戏往往都有很多的支线剧情，现在 JYY 想花费最少的时间看完所有的支线剧情。

JYY 现在所玩的 RPG 游戏中，一共有 $n$ 个剧情点，由 $1$ 到 $n$ 编号，第 $i$ 个剧情点可以根据 JYY 的不同的选择，而经过不同的支线剧情，前往 $K_i$ 种不同的新的剧情点。当然 $K_i$ 如果为 $0$，则说明 $i$ 号剧情点是游戏的一个结局了。

JYY 观看一个支线剧情需要一定的时间。JYY 一开始处在 $1$ 号剧情点，也就是游戏的开始。显然任何一个剧情点都是从 $1$ 号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。

由于 JYY 过度使用修改器，导致游戏的「存档」和「读档」功能损坏了，所以 JYY 要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到 $1$ 号剧情点。JYY 可以在任何时刻退出游戏并重新开始。

不断开始新的游戏重复观看已经看过的剧情很是痛苦，JYY 希望花费最少的时间，看完所有不同的支线剧情。

数据范围：$1 \le n \le 300$，$0 \le K_i \le 50$，$\sum_{i = 1} ^ n K_i \le 5000$。

Solution

刚看到题目可能会想到最小链覆盖，但是发现每条链必须从起点出发，并且边有权值，我们可以尝试往网络流的方向思考。

每条边至少经过 $1$ 次可以转化为这条边的流量下界为 $1$，上界为 $\infty$，费用为花费时间。直接套用有源汇有上下界费用流求解即可。

时间复杂度：$\mathcal O(n\sum K_i f)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N = 3e2 + 5, M = 2e4 + 5;
const int INF = 0x7f7f7f7f;

int n, m, deg[N], dis[N];
int tot = 1, lnk[N], cur[N], ter[M], nxt[M], cap[M], cost[M];
bool vis[N];

void add(int u, int v, int w, int c) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot, cap[tot] = w, cost[tot] = c;
}
void addEdge(int u, int v, int w, int c) {
    add(u, v, w, c), add(v, u, 0, -c);
}
bool spfa(int s, int t) {
    memset(dis, 0x7f, sizeof(dis));
    memcpy(cur, lnk, sizeof(lnk));
    std::queue<int> q;
    q.push(s), dis[s] = 0, vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop(), vis[u] = false;
        for (int i = lnk[u]; i; i = nxt[i]) {
            int v = ter[i];
            if (cap[i] && dis[v] > dis[u] + cost[i]) {
                dis[v] = dis[u] + cost[i];
                if (!vis[v]) q.push(v), vis[v] = true;
            }
        }
    }
    return dis[t] < INF;
}
int dfs(int u, int t, int flow) {
    if (u == t) return flow;
    vis[u] = true;
    int ans = 0;
    for (int &i = cur[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (cap[i] && !vis[v] && dis[v] == dis[u] + cost[i]) {
            int x = dfs(v, t, std::min(cap[i], flow));
            if (!x) continue;
            cap[i] -= x, cap[i ^ 1] += x, flow -= x, ans += x;
            if (!flow) break;
        }
    }
    vis[u] = false;
    return ans;
}
std::pair<int, int> dinic(int s, int t) {
    int maxFlow = 0, minCost = 0;
    while (spfa(s, t)) {
        int x;
        while ((x = dfs(s, t, INF))) maxFlow += x, minCost += x * dis[t];
    }
    return std::make_pair(maxFlow, minCost);
}
int main() {
    scanf("%d", &n);
    int s = 1, t = n + 1, ans = 0;
    for (int u = 1; u <= n; u++) {
        int k;
        scanf("%d", &k);
        for (int j = 1; j <= k; j++) {
            int v, c;
            scanf("%d%d", &v, &c);
            deg[u]--, deg[v]++, ans += c;
            addEdge(u, v, INF, c);
        }
        addEdge(u, t, INF, 0);
    }
    int ss = 0, tt = n + 2;
    for (int i = 1; i <= n; i++) {
        if (deg[i] > 0) addEdge(ss, i, deg[i], 0);
        if (deg[i] < 0) addEdge(i, tt, -deg[i], 0);
    }
    addEdge(t, s, INF, 0);
    printf("%d\n", ans + dinic(ss, tt).second);
    return 0;
}