Description

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

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

JYY 观看一个支线剧情需要一定的时间. JYY 一开始处在 \(1\) 号剧情点, 也就是游戏的开始. 显然任何一个剧情点都是从 \(1\) 号剧情点可达的. 此外, 随着游戏的进行, 剧情是不可逆 的. 所以游戏保证从任意剧情点出发, 都不能再回到这个剧情点. 由于 JYY 过度使用修改器, 导致游戏的 “存档” 和 “读档” 功能损坏了, 所以 JYY 要想回到之前的剧情点, 唯一的方法就是退出当前游戏, 并开始新的游戏, 也就是回到 \(1\) 号剧情点. JYY 可以在任何时刻退出游戏并重新开始. 不断开始新的游戏重复观看已经看过的剧情是很痛苦, JYY 希望花费最少的时间, 看完所有不同的支线剧情.

Input

输入一行包含一个正整数 \(n\).

接下来 \(n\) 行, 第 \(i\) 行为 \(i\) 号剧情点的信息;

第一个整数为 \(K_i\), 接下来 \(K_i\) 个整数对,\(B_{i,j}\) 和 \(T_{i,j}\), 表示从剧情点 \(i\) 可以前往剧情点 \(B_{i,j}\), 并且观看这段支线剧情需要花费 \(T_{i,j}\) 的时间.

Output

输出一行包含一个整数, 表示 JYY 看完所有支线剧情所需要的最少时间.

Sample Input

6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0

Sample Output

24

Data Range

对于 100% 的数据满足 \(n \leq 300, 0 \leq K_i \leq 50, 1 \leq T_{i,j} \leq 300, \sum K_i \leq 5000\)

Explanation

是一个有向无环图~

所以说就是保证每一条边的流量至少为 \(1\) 的一个上下界网络流问题......

但是到现在还没有搞懂, 而且把 dist[s] >= infinit 写成 inque[s] >= infinit 是什么情况 233333 调了差不多一个小时才发现这个奇葩的错误

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 800, maxm = 50010;
const lli infinit = 0x007f7f7f7f7f7f7fll;

class ZkwMcmf
{
public:
    struct edge
    {
        int u, v;
        lli flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    lli dist[maxn];
    bool inque[maxn];
    void add_edge(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = -cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool spfa(void)
    {
        for (int i = 1; i <= n; i++)
            dist[i] = infinit, inque[i] = false;
        queue<int> que;
        que.push(t);
        dist[t] = 0, inque[t] = true;
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            inque[p] = false;
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->rev->flow && dist[p] - ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] - ep->cost;
                    if (!inque[ep->v]) {
                        que.push(ep->v);
                        inque[ep->v] = true;
                    }
                }
            continue;
        }
        // if (inque[s] == infinit)
        if (dist[s] >= infinit)
            return false;
        return true;
    }
    lli max_flow;
    lli min_cost;
    lli dfs(int p, lli flow)
    {
        inque[p] = true;
        if (p == t)
            return flow;
        lli sum = 0;
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (ep->flow && !inque[ep->v] && dist[p] - ep->cost == dist[ep->v]) {
                lli tmp = dfs(ep->v, min(flow - sum, ep->flow));
                ep->flow -= tmp;
                ep->rev->flow += tmp;
                min_cost += tmp * ep->cost;
                sum += tmp;
                if (sum >= flow)
                    return flow;
            }
        return sum;
    }
    void eval(void)
    {
        memset(inque, 0, sizeof(inque));
        max_flow = 0;
        min_cost = 0;
        while (spfa()) {
            inque[t] = true;
            while (inque[t]) {
                memset(inque, 0, sizeof(inque));
                max_flow += dfs(s, infinit);
            }
        }
        return ;
    }
} graph;

int n;

int main(int argc, char** argv)
{
    scanf("%lld", &n);
    graph.n = n + 2;
    graph.s = n + 1;
    graph.t = n + 2;
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        graph.add_edge(i, graph.t, x, 0);
        graph.add_edge(i, 1, infinit, 0);
        for (int j = 1; j <= x; j++) {
            lli b, t; // Target, cost
            scanf("%lld%lld", &b, &t);
            graph.add_edge(i, b, infinit, t);
            graph.add_edge(graph.s, b, 1, t);
        }
    }
    // Evaluate and return result
    graph.eval();
    lli res = graph.min_cost;
    printf("%lld\n", res);
    return 0;
}