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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1510, M = 3e3 + 10, inf = 15e6;
bool notrt[N];
int n, rt, s[N], f[N][3];
int idx, hd[N], nxt[M], edg[M];
int dfs(int, int);
int cal(int x, bool op)
{
if (op)
{
int res = s[x];
for (int i = hd[x]; ~i; i = nxt[i])
res += dfs(edg[i], 0);
return res;
}
else
{
int res = 0;
for (int i = hd[x]; ~i; i = nxt[i])
res += min(dfs(edg[i], 1), dfs(edg[i], 2));
return res;
}
}
int dfs(int x, int op)
{
if (~f[x][op])
return f[x][op];
if (op == 0)
f[x][op] = min(cal(x, 0), cal(x, 1));
else if (op == 1)
f[x][op] = cal(x, 1);
else if (op == 2)
{
int s = 0;
for (int i = hd[x]; ~i; i = nxt[i])
s += min(dfs(edg[i], 1), dfs(edg[i], 2));
f[x][op] = inf;
for (int i = hd[x]; ~i; i = nxt[i])
f[x][op] = min(f[x][op], s - min(dfs(edg[i], 1), dfs(edg[i], 2)) + dfs(edg[i], 1));
}
return f[x][op];
}
void add(int a, int b)
{
nxt[++idx] = hd[a];
hd[a] = idx;
edg[idx] = b;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
hd[i] = -1;
for (int i = 1, a, m; i <= n; i++)
{
scanf("%d", &a);
scanf("%d%d", &s[a], &m);
for (int b; m; m--)
{
scanf("%d", &b);
add(a, b);
notrt[b] = true;
}
}
for (int i = 1; i <= n; i++)
if (!notrt[i])
rt = i;
memset(f, -1, sizeof f);
printf("%d", min(dfs(rt, 1), dfs(rt, 2)));
return 0;
}
|