Skip to content
Snippets Groups Projects
Select Git revision
  • master default protected
1 result

G.cpp

Blame
  • 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;
    }