Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- #define forall(it,v) for(auto it=v.begin();it!=v.end();++it)
- #define zero(v) memset(v, 0, sizeof(v))
- #define pb push_back
- #define sz(v) ((int)v.size())
- #define INF 1e18
- const int MAX = 2050;
- int nodes, src, dst;
- int dist[MAX], q[MAX], work[MAX];
- int mid;
- struct Edge {
- int to, rev;
- ll f, cap;
- Edge(int to, int rev, ll f, ll cap) : to(to), rev(rev), f(f), cap(cap) {}
- };
- vector<Edge> G[MAX];
- void addEdge(int s, int t, ll cap){
- G[s].pb(Edge(t, sz(G[t]), 0, cap)), G[t].pb(Edge(s, sz(G[s])-1, 0, 0));}
- bool dinic_bfs(){
- fill(dist, dist+nodes, -1), dist[src]=0;
- int qt=0; q[qt++]=src;
- for(int qh=0; qh<qt; qh++){
- int u =q[qh];
- forall(e, G[u]){
- int v=e->to;
- if(dist[v]<0 && e->f < e->cap)
- dist[v]=dist[u]+1, q[qt++]=v;
- }
- }
- return dist[dst]>=0;
- }
- ll dinic_dfs(int u, ll f){
- if(u==dst) return f;
- for(int &i=work[u]; i<sz(G[u]); i++){
- Edge &e = G[u][i];
- if(e.cap<=e.f) continue;
- int v=e.to;
- if(dist[v]==dist[u]+1){
- ll df=dinic_dfs(v, min(f, e.cap-e.f));
- if(df>0){
- e.f+=df, G[v][e.rev].f-= df;
- return df; }
- }
- }
- return 0;
- }
- ll maxFlow(int _src, int _dst){
- src=_src, dst=_dst;
- ll result=0;
- while(dinic_bfs()){
- fill(work, work+nodes, 0);
- while(ll delta=dinic_dfs(src,INF))
- result+=delta;
- }
- return result; }
- int caps[MAX];
- int ret[MAX];
- long long sum = 0;
- vector<tuple<int,int,int> >edges;
- int main() {
- ios::sync_with_stdio(false);cin.tie(0);
- nodes = 2050;
- int to, from, m;
- //from 0 ... from, to from ... to + from, src to + from, dst to + from + 1
- cin >> to >> from >> m;
- for (int i = 0, u; i < to; i++) {
- cin >> caps[i];
- sum += caps[i];
- }
- for (int i = 0, u; i < from; i++) {
- cin >> ret[i];
- }
- while (m --) {
- int u, v, t;
- cin >> u >> v >> t;
- u--,v--;
- edges.emplace_back(v, u, t);
- }
- //cout << "END LECTURE " << endl;
- int a = 0, b = 1000001;
- while(b - a > 1) {
- mid = (a + b) >> 1;
- //cout << "@ @ @ " << mid << endl;
- for (int i = 0; i < MAX; i++)G[i].clear();
- for (int i = 0; i < to; i++) {
- //cout << from + i << " " << from + to + 1 << " INT_MAX"<< endl;
- addEdge(from + i, to + from + 1, caps[i]);
- }
- //cout << " ############# " << endl;
- for (int i = 0; i < from; i++) {
- //cout << to + from << " " << i << " "<< ret[i]<< endl;
- addEdge(to + from, i, ret[i]);
- }
- //cout << "EDGES " << endl;
- for (auto edge:edges) {
- int f = get<0>(edge);
- int t = get<1>(edge);
- int time = get<2>(edge);
- if (time <= mid) {
- //cout << f << " " << t + to << " " << caps[t]<< endl;
- addEdge(f, t + from, caps[t]);
- }
- }
- ll ans = maxFlow(to + from, to + from + 1);
- //cout << ans << endl;
- if (ans == sum)b = mid;
- else a = mid;
- }
- if (b == 1000001) cout << -1;
- else cout << b << "\n";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement