水题记录(九)

题目名称 树的路径覆盖 建筑抢修 生日聚会 极地旅行社 星际竞速 神秘大三角 冷冻波
标签 动态规划 贪心 + 堆 动态规划 动态树 费用流 计算几何 计算几何 + 网络流
来源 BZOJ 1907 BZOJ 1029 BZOJ 1037 BZOJ 2843 BZOJ 1927 Luogu 1355 BZOJ 1822

BZOJ 1907

题意

题解

一开始想当然认为树链剖分中的按重路径剖分就是但,然后WA的很惨。。不信你试试菊花图,后来才知道这是个树型DP,看来还是我太菜了。。。特判了$1$才过

附赠一组数据

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
input 
5
7
1 2
1 3
2 4
2 5
3 6
3 7
7
1 2
2 3
2 4
4 6
5 6
6 7
5
1 2
1 3
1 4
1 5
1
2
1 2
output
3
3
3
1
1
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
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
const int oo = 1e9;
const int maxn = 1e4 + 10;
int dp[maxn][2];
std::vector<int>G[maxn];
void dfs(int u, int f) {
if (G[u].size() == 1 && f != 0)
return void(dp[u][0] = dp[u][1] = 1);
int dt1 = oo, dt2 = oo, sum = 0;
for (int i = G[u].size() - 1; ~i; i--) {
int v = G[u][i]; if (v == f) continue;
dfs(v, u);
sum += dp[v][0];
if (dt1 > dp[v][1] - dp[v][0])
dt2 = dt1, dt1 = dp[v][1] - dp[v][0];
else
dt2 = std::min(dt2, dp[v][1] - dp[v][0]);
}
dp[u][0] = sum + dt1 + dt2 - 1;
dp[u][1] = sum + dt1;
dp[u][0] = std::min(dp[u][0], dp[u][1]);
}
int main() {
int T; scanf("%d", &T);
while (T--) {
int n; scanf("%d", &n);
if (n == 1) { printf("1\n"); continue; }
for (int i = 1; i < n; i++) {
int x, y; scanf("%d%d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 0); printf("%d\n", dp[1][0]);
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) G[i].clear();
}
}

BZOJ 1029

题意

小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T部落消灭了所有z部落的
入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤,如果不尽快修复的话,这些建筑设施将会完全
毁坏。现在的情况是:T部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需
要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在一
段时间之内没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序,以抢修尽可能多
的建筑。

题解

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
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
vector<pair<ll, ll> >T;
priority_queue<ll>Pq; ll sum;
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x, y; scanf("%d%d", &x ,&y);
T.push_back(make_pair(y, x));
}
sort(T.begin(), T.end());
for (vector<pair<ll, ll> >::iterator it = T.begin(); it != T.end(); it++) {
if (it->second + sum <= it->first) {
Pq.push(it->second); sum += it->second;
}
else {
if (it->second < Pq.top()) {
sum -= Pq.top(); Pq.pop();
sum += it->second; Pq.push(it->second);
}
}
}
printf("%d\n", int(Pq.size()));
}

生日聚会

题意

今天是hidadz小朋友的生日,她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中,打算坐成一排玩游戏。为了游戏不至于无聊,就座的方案应满足如下条件:对于任意连续的一段,男孩与女孩的数目之差不超过k。很快,小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现,这样的就座方案其实是很多的,所以大家很快就找到了一种,那么到底有多少种呢?热爱数学的hidadz和她的朋友们开始思考这个问题
…… 假设参加party的人中共有n个男孩与m个女孩,你是否能解答Susie和hidadz的疑问呢?由于这个数目可能很多,他们只想知道这个数目除以12345678的余数。

题解

设 $dp[i][j][x][y]$ 表示现在用了 $i$ 个男生 $j$ 个女生,在排列的后缀中,男生最多比女生多 $x$ 人,女生最多比男生多 $y$ 人,考虑以下两种转移

  • 在末尾放一个男生,转移到状态 $dp[i + 1][j][x + 1][max(j - 1, 0)]$
  • 在末尾放一个女生,转移到状态 $dp[i][j + 1][max(x - 1, 0)][j + 1]$
    水过~
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    #include <bits/stdc++.h> 
    using namespace std;
    const int oo = 12345678;
    int dp[160][160][22][22];
    int main() {
    int n, m, k; scanf("%d%d%d", &n, &m, &k);
    dp[0][0][0][0] = 1;
    for (int i = 0; i <= n; i++)
    for (int j = 0; j <= m; j++)
    for (int x = 0; x <= k; x++)
    for (int y = 0; y <= k; y++) {
    (dp[i + 1][j][x + 1][max(y - 1, 0)] += dp[i][j][x][y]) %= oo;
    (dp[i][j + 1][max(x - 1, 0)][y + 1] += dp[i][j][x][y]) %= oo;
    }
    int ans = 0;
    for (int x = 0; x <= k; x++)
    for (int y = 0; y <= k; y++)
    (ans += dp[n][m][x][y]) %= oo;
    printf("%d\n", ans);
    }

BZOJ 2843

题意

同洛谷模板,维护的是从x到y的权值和

题解

lct 水题

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
#define nl NULL
const int maxn = 1e5 + 10;
namespace lct {
struct node {
node *father, *son[2];
int value, sum; bool rev;
node(int val = 0) {
value = val; sum = val; rev = false;
son[0] = son[1] = father = nl;
}
bool is_root() {
if (!father) return true;
return father->son[0] != this && father->son[1] != this;
}
bool who() {
return father->son[1] == this;
}
void reverse() {
swap(son[0], son[1]); rev = !rev;
}
void pushdown_once() {
if (!rev) return; rev = false;
if (son[0]) son[0]->reverse();
if (son[1]) son[1]->reverse();
}
void pushdown() {
if (!is_root()) father->pushdown(); pushdown_once();
}
void maintain() {
sum = value;
if (son[0]) sum += son[0]->sum;
if (son[1]) sum += son[1]->sum;
}
void rotate() {
node *f = father, *g = f->father;
bool a = who(), b = !a;
f->son[a] = son[b];
if (son[b])
son[b]->father = f;
son[b] = f;
father = g;
if (!f->is_root())
g->son[f->who()] = this;
f->father = this;
f->maintain(); maintain();
}
void splay() {
for (pushdown(); !is_root(); rotate())
if (!father->is_root())
if (who() ^ father->who()) rotate();
else father->rotate();
}
void access() {
for (node *y = nl, *x = this; x; y = x, x = x->father)
x->splay(), x->son[1] = y, x->maintain();
}
void make_root() {
access(); splay(); reverse();
}
node *root() {
access(); splay();
for (node *x = this; ; x = x->son[0])
if (!x->son[0]) return x;
}
}*T[maxn];
bool con(int x, int y) {
return T[x]->root() == T[y]->root();
}
void link(int x, int y) {
T[x]->make_root(); T[x]->father = T[y];
}
void cut(int x, int y) {
T[x]->make_root(); T[y]->access(); T[y]->splay();
T[x]->father = T[y]->son[0] = nl; T[y]->maintain();
}
void change(int x, int y) {
T[x]->splay(); T[x]->value = y; T[x]->maintain();
}
int query(int x, int y) {
T[x]->make_root(); T[y]->access();
T[x]->splay(); return T[x]->sum;
}
}
using namespace lct;
char op[20];
int main() {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x); T[i] = new node(x);
}
int m; scanf("%d", &m);
while (m--) {
int x, y; scanf("%s%d%d", op, &x, &y);
if (op[0] == 'b') {
if (con(x, y)) puts("no");
else puts("yes"), link(x, y);
}
if (op[0] == 'p') change(x, y);
if (op[0] == 'e') {
if (!con(x, y)) puts("impossible");
else {
printf("%d\n", query(x, y));
}
}
}
return 0;
}

BZOJ 1927

题意

10年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一,夺得这个项目的冠军无疑是很多人的
梦想,来自杰森座α星的悠悠也是其中之一。赛车大赛的赛场由N颗行星和M条双向星际航路构成,其中每颗行星都
有一个不同的引力值。大赛要求车手们从一颗与这N颗行星之间没有任何航路的天体出发,访问这N颗行星每颗恰好
一次,首先完成这一目标的人获得胜利。由于赛制非常开放,很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠
驾驶的赛车名为超能电驴,这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物,超能电驴有
两种移动模式:高速航行模式和能力爆发模式。在高速航行模式下,超能电驴会展开反物质引擎,以数倍于光速的
速度沿星际航路高速航行。在能力爆发模式下,超能电驴脱离时空的束缚,使用超能力进行空间跳跃——在经过一
段时间的定位之后,它能瞬间移动到任意一个行星。天不遂人愿,在比赛的前一天,超能电驴在一场离子风暴中不
幸受损,机能出现了一些障碍:在使用高速航行模式的时候,只能由每个星球飞往引力比它大的星球,否则赛车就
会发生爆炸。尽管心爱的赛车出了问题,但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者——
你,请你为他安排一条比赛的方案,使得他能够用最少的时间完成比赛。

题解

建图可以参考餐巾计划

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
#include <bits/stdc++.h>
using namespace std;
namespace MinCostMaxFlow {
const int maxm = 2e5;
const int maxn = 2e4;
const int inf = 1e9;
struct edge {
int to, next, cap, dis;
edge(){}
edge(int x, int y, int z, int w) {
to = x; next = y; cap = z; dis = w;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
void add(int x, int y, int c, int d) {
e[++edgeCnt] = edge(y, head[x], c, d); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0,-d); head[y] = edgeCnt;
}
int dis[maxn]; bool inq[maxn], vis[maxn];
bool spfa(int s, int t) {
memset(dis, -1, sizeof(int) * (t + 1));
//memset(dis, -1, sizeof(dis));
std::queue<int>q; q.push(t); dis[t] = 0;
while (q.size()) {
int u = q.front(); q.pop(); inq[u] = false;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to; if (!e[i ^ 1].cap) continue;
if (!~dis[v] || dis[v] > dis[u] + e[i ^ 1].dis) {
dis[v] = dis[u] + e[i ^ 1].dis;
if (!inq[v]) inq[v] = true, q.push(v);
}
}
}
return dis[s] != -1;
}
int dfs(int u, int t, int f) {
vis[u] = true; if (u == t || !f) return f; int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to; if (!e[i].cap || vis[v]) continue;
if (dis[v] != dis[u] - e[i].dis) continue;
int a = dfs(v, t, std::min(e[i].cap, f));
e[i].cap -= a; e[i ^ 1].cap += a; f -= a; r += a;
}
return r;
}
std::pair<int,int> zkw(int s, int t) {
int flow = 0, cost = 0, tmp;
while (spfa(s, t)) {
memset(vis, false, sizeof(vis));
tmp = dfs(s, t, inf);
flow += tmp; cost += tmp * dis[s];
}
return std::make_pair(flow, cost);
}
void solve() {
#define S (n + 1) << 1
#define T (n + 1) << 1 | 1
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x);
add(S, i << 1, 1, 0);
add(i << 1 | 1, T, 1, 0);
add(S, i << 1 | 1, 1, x);
}
while (m--) {
int u, v, w; scanf("%d%d%d", &u, &v, &w);
if (u > v) swap(u, v);
add(u << 1, v << 1 | 1, 1, w);
}
printf("%d\n", zkw(S, T).second);
}
}

int main() {
MinCostMaxFlow::solve();
}

Luogu 1355

题意

判断一个点与已知三角形的位置关系。

  • 若点在三角形内(不含边界),输出1
  • 三角形外(不含边界),输出2
  • 三角形边界上(不含顶点),输出3
  • 若点在三角形顶点上,输出4。

    题解

    计算几何题目是不是 50 行起步啊。。。这种水题我打了 90 行。。。
    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
    87
    88
    89
    #include <bits/stdc++.h>
    namespace geometry {
    const double ee = 1e-9;
    const double oo = 1e15;
    char tmp;
    bool equ(double x, double y) {
    return fabs(x - y) <= ee;
    }
    struct vec {
    double x, y;
    vec() { x = y = 0; }
    vec(double x, double y) : x(x), y(y) {}
    void read() {
    std::cin >> tmp >> x >> tmp >> y >> tmp;
    }
    };
    struct seg {
    vec a, b;
    seg() {}
    seg(vec a, vec b) : a(a), b(b) {}
    };
    vec operator + (vec a, vec b) {
    return vec(a.x + b.x, a.y + b.y);
    }
    vec operator - (vec a, vec b) {
    return vec(a.x - b.x, a.y - b.y);
    }
    vec operator * (vec a, double b) {
    return vec(a.x * b, a.y * b);
    }
    vec operator * (double b, vec a) {
    return vec(a.x * b, a.y * b);
    }
    vec operator / (vec a, double b) {
    return vec(a.x / b, a.y / b);
    }
    bool operator == (vec a, vec b) {
    return equ(a.x, b.x) && equ(a.y, b.y);
    }
    double operator * (vec a, vec b) {
    return a.x * b.x + a.y * b.y;
    }
    double operator ^ (vec a, vec b) {
    return a.x * b.y - a.y * b.x;
    }
    double dis(vec a, vec b) {
    return sqrt((a - b) * (a - b));
    }

    bool ptInRect(vec p, seg l) {
    vec a = l.a, b = l.b;
    if (p.x > std::max(a.x, b.x)) return false;
    if (p.x < std::min(a.x, b.x)) return false;
    if (p.y > std::max(a.y, b.y)) return false;
    if (p.y < std::min(a.y, b.y)) return false;
    return true;
    }
    bool ptOnSeg(vec p, seg l) {
    return equ((l.a - l.b) ^ p, 0) && ptInRect(p, l);
    }
    bool segCntLine(seg s, seg l) {
    return ((s.a - l.a) ^ (l.b - l.a)) * ((s.b - l.a) ^ (l.b - l.a)) >= 0;
    }
    bool segCrossSeg(seg l1, seg l2) {
    if (!ptInRect(l1.a, l2)) return false;
    if (!ptInRect(l1.b, l2)) return false;
    if (!segCntLine(l1, l2)) return false;
    if (!segCntLine(l2, l1)) return false;
    return true;
    }
    }
    using namespace geometry;
    int main() {
    vec a, b, c, d;
    a.read();
    b.read();
    c.read();
    d.read();
    if (a == d) return 0 * puts("4");
    if (b == d) return 0 * puts("4");
    if (c == d) return 0 * puts("4");
    if (ptOnSeg(d, seg(a, b))) return 0 * puts("3");
    if (ptOnSeg(d, seg(a, c))) return 0 * puts("3");
    if (ptOnSeg(d, seg(b, c))) return 0 * puts("3");
    if (((d - a) ^ (d - b)) * ((d - b) ^ (d - c)) < 0) return 0 * puts("2");
    if (((d - b) ^ (d - c)) * ((d - c) ^ (d - a)) < 0) return 0 * puts("2");
    if (((d - c) ^ (d - a)) * ((d - a) ^ (d - b)) < 0) return 0 * puts("2");
    return 0 * puts("1");
    }

BZOJ 1822

题意

$WJJ$喜欢“魔兽争霸”这个游戏。在游戏中,巫妖是一种强大的英雄,它的技能$Frozen Nova$每次可以杀死一个小精灵。我们认为,巫妖和小精灵都可以看成是平面上的点。 当巫妖和小精灵之间的直线距离不超过$R$,且巫妖看到小精灵的视线没有被树木阻挡(也就是说,巫妖和小精灵的连线与任何树木都没有公共点)的话,巫妖就可以瞬间杀灭一个小精灵。在森林里有$N$个巫妖,每个巫妖释放$FrozenNova$之后,都需要等待一段时间,才能再次施放。不同的巫妖有不同的等待时间和施法范围,但相同的是,每次施放都可以杀死一个小精灵。 现在巫妖的头目想知道,若从0时刻开始计算,至少需要花费多少时间,可以杀死所有的小精灵?

题解

先暴力找出每个巫妖能打到的小精灵,然后二份答案,网络流检验是否满流即可

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
namespace flow {
const int maxm = 1e5 + 10;
const int maxn = 1e4 + 10;
const int oo = 1e9;
struct edge {
int to, next, cap;
edge() {}
edge(int x, int y, int z) {
to = x; next = y; cap = z;
}
}e[maxm];
int head[maxn], edgeCnt = 1;
int deep[maxn];
void add(int x, int y, int w) {
e[++edgeCnt] = edge(y, head[x], w); head[x] = edgeCnt;
e[++edgeCnt] = edge(x, head[y], 0); head[y] = edgeCnt;
}
bool bfs(int s, int t) {
memset(deep, 0, sizeof(int) * (t + 1));
std::queue<int>q; q.push(s); deep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v]) continue;
deep[v] = deep[u] + 1; q.push(v);
}
}
return deep[t];
}
int dfs(int u, int t, int f) {
if (u == t || !f) return f;
int r = 0;
for (int i = head[u]; i && f; i = e[i].next) {
int v = e[i].to;
if (!e[i].cap || deep[v] != deep[u] + 1) continue;
int a = dfs(v, t, std::min(f, e[i].cap));
r += a; f -= a; e[i].cap -= a; e[i ^ 1].cap += a;
}
return r;
}
int dinic(int s, int t) {
int r = 0;
while (bfs(s, t))
r += dfs(s, t, oo);
return r;
}
void clear(int n) {
memset(head, 0, sizeof(int) * (n + 1)); edgeCnt = 1;
}
}
namespace geo {
const double ee = 1e-9;
const double oo = 1e15;
bool equ(double x, double y) { return fabs(x - y) <= ee; }
struct vec {
double x, y; vec() {}
vec(double x, double y) : x(x), y(y) {}
friend vec operator + (vec a, vec b) { return vec(a.x + b.x, a.y + b.y); }
friend vec operator - (vec a, vec b) { return vec(a.x - b.x, a.y - b.y); }
friend vec operator * (vec a, double b) { return vec(a.x * b, a.y * b); }
friend vec operator * (double b, vec a) { return a * b; }
friend vec operator / (vec a, double b) { return a * (1 / b); }
friend double operator * (vec a, vec b) { return a.x * b.x + a.y * b.y; } //点积
friend double operator ^ (vec a, vec b) { return a.x * b.y - a.y * b.x; } //叉积
friend bool operator < (vec a, vec b) { return a.x < b.x || (equ(a.x, b.x) && a.y < b.y); }
friend bool operator == (vec a, vec b) { return equ(a.x, b.x) && equ(a.y, b.y); }
void read() { scanf("%lf%lf", &x, &y); }
double dis() { return sqrt(*this * *this); } //模长
vec normal() { return vec(-y, x) / dis(); } //法向量
};
typedef vec poi;
struct seg {
poi a, b; seg() {}
seg(vec a, vec b) : a(a), b(b) {}
};
typedef seg rec;
bool InRec(poi p, rec r) {
if (p.x > std::max(r.a.x, r.b.x)) return false;
if (p.x < std::min(r.a.x, r.b.x)) return false;
if (p.y > std::max(r.a.y, r.b.y)) return false;
if (p.y < std::min(r.a.y, r.b.y)) return false;
return true;
}
}
const int maxn = 1e3;
geo::poi A[maxn], B[maxn], C[maxn];
int Ar[maxn], At[maxn], Cr[maxn];
bool cover[maxn];
int n, m, k;
bool check(int x, int y) {
geo::vec u = B[y] - A[x];
double dxy = u.dis();
if (dxy > Ar[x]) return false;
for (int i = 1; i <= k; i++) {
geo::vec v = C[i] - A[x];
double dli = (v ^ u) / dxy;
if (fabs(dli) > Cr[i]) continue;
geo::poi h = C[i] + (u.normal() * dli);
if (!geo::InRec(h, geo::rec(A[x], B[y]))) continue;
return false;
}
return true;
}
std::vector<int>G[maxn];
#define S (n + m + 1)
#define T (n + m + 2)
bool ok(int ans) {
flow::clear(n + m + 2);
for (int i = 1; i <= n; i++)
flow::add(S, i, (ans / At[i]) + 1);
for (int j = 1; j <= m; j++)
flow::add(j + n, T, 1);
for (int i = 1; i <= m; i++)
for (int j = G[i].size() - 1; ~j; j--)
flow::add(i, G[i][j] + n, 1);
return flow::dinic(S, T) == m;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
A[i].read(), scanf("%d%d", &Ar[i], &At[i]);
for (int i = 1; i <= m; i++) B[i].read();
for (int i = 1; i <= k; i++)
C[i].read(), scanf("%d", &Cr[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (check(i, j)) G[i].push_back(j), cover[j] = true;
for (int i = 1; i <= m; i++)
if (!cover[i]) return puts("-1") * 0;
int l = 0, r = 4000000;
while (l < r) {
int mid = l + r >> 1;
if (ok(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
}