Select Git revision
-
Bruno Freitas Tissei authored
Signed-off-by:
Bruno Freitas Tissei <bft15@inf.ufpr.br>
Bruno Freitas Tissei authoredSigned-off-by:
Bruno Freitas Tissei <bft15@inf.ufpr.br>
G.cpp 2.58 KiB
#include <bits/stdc++.h>
#define MAX 3010
#define EPS 1e-6
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define llinf 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define pb push_back
#define ende '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mset(x, y) memset(&x, (y), sizeof(x))
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
struct edge {
int u;
int flow, cap;
int rev;
edge(int u, int flow, int cap, int rev) :
u(u), flow(flow), cap(cap), rev(rev)
{}
};
int depth[MAX];
int start[MAX];
vector<edge> graph[MAX];
void add_edge(int s, int t, int c) {
edge forward(t, 0, c, graph[t].size());
edge backward(s, 0, 0, graph[s].size());
graph[s].pb(forward);
graph[t].pb(backward);
}
bool bfs(int s, int t) {
queue<int> Q;
Q.push(s);
mset(depth, -1);
depth[s] = 0;
while (!Q.empty()) {
int v = Q.front(); Q.pop();
for (auto i : graph[v]) {
if (depth[i.u] == -1 && i.flow < i.cap) {
depth[i.u] = depth[v] + 1;
Q.push(i.u);
}
}
}
return depth[t] != -1;
}
int dfs(int s, int t, int flow) {
if (s == t)
return flow;
for ( ; start[s] < graph[s].size(); ++start[s]) {
edge &e = graph[s][start[s]];
if (depth[e.u] == depth[s] + 1 && e.flow < e.cap) {
int min_flow = dfs(e.u, t, min(flow, e.cap - e.flow));
if (min_flow > 0) {
e.flow += min_flow;
graph[e.u][e.rev].flow -= min_flow;
return min_flow;
}
}
}
return 0;
}
int dinic(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
mset(start, 0);
while (int flow = dfs(s, t, inf))
ans += flow;
}
return ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int p, r, c; cin >> p >> r >> c;
int s = 0, t = MAX - 1;
int dem = 0;
vector<int> dems(p);
for (auto &i : dems) {
cin >> i;
dem += i;
}
vector<int> ests(r);
for (auto &i : ests) cin >> i;
vector<pair<ii,int>> total;
for (int i = 0; i < c; ++i) {
int a, b, T; cin >> a >> b >> T;
total.pb(make_pair(ii(a, b), T));
}
int L = 0, R = 1010101;
for (int i = 0; i < 20; ++i) {
int m = (L + R) / 2;
for (int j = 0; j < p; ++j)
add_edge(j + 1 + r, t, dems[j]);
for (int j = 0; j < r; ++j)
add_edge(s, j + 1, ests[j]);
for (auto j : total)
if (j.se <= m)
add_edge(j.fi.se, j.fi.fi + r, inf);
if (dinic(s, t) < dem)
L = m + 1;
else
R = m - 1;
for (int j = 0; j < MAX; ++j)
graph[j].clear();
}
cout << (L >= 1010101 ? -1 : L) << ende;
return 0;
}