BZOJ3876【JSOI2014】支线剧情 <带下界的费用流>

Problem

【JSOI2014】支线剧情

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Background

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

Description

$\mathrm{JYY}$现在所玩的$\mathrm{RPG}$游戏中，一共有$N$个剧情点，由$1$到$N$编号，第$i$个剧情点可以根据$\mathrm{JYY}$的不同的选择，而经过不同的支线剧情，前往$K_i$种不同的新的剧情点。当然如果为$0$，则说明$i$号剧情点是游戏的一个结局了。
$\mathrm{JYY}$观看一个支线剧情需要一定的时间。$\mathrm{JYY}$一开始处在$1$号剧情点，也就是游戏的开始。显然任何一个剧情点都是从$1$号剧情点可达的。此外，随着游戏的进行，剧情是不可逆的。所以游戏保证从任意剧情点出发，都不能再回到这个剧情点。
由于$\mathrm{JYY}$过度使用修改器，导致游戏的“存档”和“读档”功能损坏了，所以$\mathrm{JYY}$要想回到之前的剧情点，唯一的方法就是退出当前游戏，并开始新的游戏，也就是回到$1$号剧情点。$\mathrm{JYY}$可以在任何时刻退出游戏并重新开始。
不断开始新的游戏重复观看已经看过的剧情是很痛苦，$\mathrm{JYY}$希望花费最少的时间，看完所有不同的支线剧情。

Input

输入一行包含一个正整数$N$。
接下来$N$行，第$i$行为$i$号剧情点的信息：第一个整数为$K_i$，接下来$K_i$个整数对，$B_{i,j}$和$T_{i,j}$，表示从剧情点$i$可以前往剧情点$B_{i,j}$，并且观看这段支线剧情需要花费$T_{i,j}$的时间。

Output

输出一行包含一个整数，表示$\mathrm{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

Explanation

$\mathrm{JYY}$需要重新开始$3$次游戏，加上一开始的一次游戏，$4$次游戏的进程是$1\to2\to4$,$1\to2\to5$,$1\to3\to5$和$1\to3\to6$。

Hint

$100\%$的数据满足$N\le300$,$0\le K_i\le50$,$1\le T_{i,j}\le300$,$\sum_{i=1}^{n}{K_i}\le5000$

标签：带下界的费用流

Solution

无源无汇带下界最小费用可行流。

将原图直接放入网络流，其中每条边流量下界为$1$，上界为$\infty$；每个点向$1$连一条流量下界为$0$，上界为$\infty$，费用为$0$的边。这样就转化为求此图的最小费用可行流。
将原图中每条边拆一个流量为$1$费用不变的边出来，这样若这条边满载后，只需要流量守恒即可。对于每个点，令入度为$into$，出度为$outo$。则经过其的流量一定是$\max(into,outo)$。如此拆出来的流量为$1$的边可以以出入度的限制的形式出现，而不必真正建出这些边使其满载。而对于入度和出度不等的边，我们新建源汇，从源点补流或分流到汇点即可。

建图：

• 对于原图中每条边$u\to v$长度$c$，连边$u\to v$流量$\infty$费用$c$
• 对于非$1$号点的点$i$，连边$i\to 1$流量$\infty$费用$0$
• 对于点$i$，计算其入度$into$和出度$outo$
  • 若$into>outo$，连边$S\to i$流量$into-outo$费用$0$
  • 若$into < outo$，连边$i\to T$流量$outo-into$费用$0$

跑最小费用最大流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 300
#define MAX_M 20000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, s, t, tot, deg[MAX_N+5];
int cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 0, t = n+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que; bool inq[MAX_N+5]; int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front(); que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false; int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += flow*d[t]; return true;
}
int main() {
    read(n), init();
    for (int u = 1, k; u <= n; u++) {
        read(k);
        for (int i = 0, v, c; i < k; i++)
            read(v), read(c), addedge(u, v, INF, c), 
            deg[u]--, deg[v]++, tot += c;
        if (u^1) addedge(u, 1, INF, 0);
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] > 0) addedge(s, i, deg[i], 0);
        else if (deg[i] < 0) addedge(i, t, -deg[i], 0);
    while (SPFA()) ;
    return printf("%d\n", mic+tot), 0;
}