「BZOJ3876」[AHOI2014&JSOI2014]支线剧情

Description

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

JYY 现在所玩的 RPG 游戏中,一共有 NN 个剧情点,由 11NN 编号,第 ii 个剧情点可以根据 JYY 的不同的选择,而经过不同的支线剧情,前往 KiK_i 种不同的新的剧情点。当然 KiK_i 如果为 00,则说明 ii 号剧情点是游戏的一个结局了。
JYY 观看一个支线剧情需要一定的时间。JYY 一开始处在 11 号剧情点,也就是游戏的开始。显然任何一个剧情点都是从 11 号剧情点可达的。此外,随着游戏的进行,剧情是不可逆的。所以游戏保证从任意剧情点出发,都不能再回到这个剧情点。

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

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

Input

输入一行包含一个正整数 NN
接下来 NN 行,第 ii 行为 ii 号剧情点的信息;
第一个整数为 KiK_i,接下来 KiK_i 个整数对,BijB_{ij}TijT_{ij},表示从剧情点 ii 可以前往剧情点 BijB_{ij},并且观看这段支线剧情需要花费的时间为 TijT_{ij}

Output

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

Sample Input

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

Sample Output

1
24

HINT

对于100%100\%的数据,N300, 0Ki50, 1Tij300, Ki5000N \leq 300,\ 0 \leq K_i \leq 50,\ 1 \leq T_{ij} \leq 300,\ \sum K_i \leq 5000

Solution

有源汇上下界网络流。

如图,边(u,v)(u,v)要求流量范围为[x,y][x,y]
从超级源点SS连向vv容量为xx的边,表示vv点至少有xx流量流出。
uu连向超级汇点TT容量为xx的边,表示uu点至少有xx流量流入。
因为是有源点和汇点的,从汇点连源点容量为infinf的边。
跑一遍最大流,如果满流的话就okok了。

force

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 310, M = 310 * 310 * 3;

struct Edge {
int u, v, nxt,f, w;
}e[M*2];
int head[N], en = 1;
void addedge(int x, int y, int z, int w) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z, e[en].w = w;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0, e[en].w = -w;
}
const int inf = 1e9;
int s, t;
int d[N], pre[N], inc[N];
bool inq[N];
bool spfa() {
for(int i = 1; i <= t; ++i) d[i] = inf;
d[s] = 0;
inc[s] = inf;
queue<int>q;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
inq[x] = 0;
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f && d[e[i].v] > d[x] + e[i].w) {
d[e[i].v] = d[x] + e[i].w;
pre[e[i].v] = i;
inc[e[i].v] = min(inc[x], e[i].f);
if(!inq[e[i].v]) inq[e[i].v] = 1, q.push(e[i].v);
}
}
return d[t] < inf;
}
int KM() {
int x = t;
while(x != s) {
e[pre[x]].f -= inc[t];
e[pre[x] ^ 1].f += inc[t];
x = e[pre[x]].u;
}
return inc[t] * d[t];
}
int n;
int main() {
n = read();
s = n + 2, t = n + 3;
for(int i = 1; i <= n; ++i) {
int m = read();
for(int j = 1; j <= m; ++j) {
int x = read(), y = read();
addedge(i, x, inf, y);
addedge(s, x, 1, y);
}
addedge(i, t, m, 0);
}
for(int i = 2; i <= n; ++i)
addedge(i, n + 1, inf, 0);
addedge(n + 1, 1, inf, 0);
int res = 0;
while(spfa()) res += KM();
writeln(res);
return 0;
}

std

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}

const int N = 310, M = 310 * 310 * 3;

struct Edge {
int u, v, nxt,f, w;
}e[M*2];
int head[N], en = 1;
void addedge(int x, int y, int z, int w) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en, e[en].f = z, e[en].w = w;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en, e[en].f = 0, e[en].w = -w;
}
const int inf = 1e9;
int s, t;
int d[N], pre[N], inc[N];
bool inq[N];
bool spfa() {
for(int i = 1; i <= t; ++i) d[i] = inf;
d[s] = 0;
inc[s] = inf;
queue<int>q;
q.push(s);
while(!q.empty()) {
int x = q.front(); q.pop();
inq[x] = 0;
for(int i = head[x]; i;i = e[i].nxt) if(e[i].f && d[e[i].v] > d[x] + e[i].w) {
d[e[i].v] = d[x] + e[i].w;
pre[e[i].v] = i;
inc[e[i].v] = min(inc[x], e[i].f);
if(!inq[e[i].v]) inq[e[i].v] = 1, q.push(e[i].v);
}
}
return d[t] < inf;
}
int KM() {
int x = t;
while(x != s) {
e[pre[x]].f -= inc[t];
e[pre[x] ^ 1].f += inc[t];
x = e[pre[x]].u;
}
return inc[t] * d[t];
}
int n, c[N];
int main() {
n = read();
s = n + 2, t = n + 3;
int res = 0;
for(int i = 1; i <= n; ++i) {
int m = read();
for(int j = 1; j <= m; ++j) {
int x = read(), y = read();
++c[x]; --c[i];
addedge(i, x, inf, y);
res += y;
}
}
for(int i = 1; i <= n; ++i) {
if(c[i] < 0) addedge(i, t, -c[i], 0);
if(c[i] > 0) addedge(s, i, c[i], 0);
}
for(int i = 2; i <= n; ++i)
addedge(i, n + 1, inf, 0);
addedge(n + 1, 1, inf, 0);
while(spfa()) res += KM();
writeln(res);
return 0;
}