Guest User

Untitled

a guest
Oct 14th, 2018
236
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define forall(it,v) for(auto it=v.begin();it!=v.end();++it)
  5. #define zero(v) memset(v, 0, sizeof(v))
  6. #define pb push_back
  7. #define sz(v) ((int)v.size())
  8. #define INF 1e18
  9.  
  10. const int MAX = 2050;
  11. int nodes, src, dst;
  12. int dist[MAX], q[MAX], work[MAX];
  13. int mid;
  14. struct Edge {
  15.     int to, rev;
  16.     ll f, cap;
  17.     Edge(int to, int rev, ll f, ll cap) : to(to), rev(rev), f(f), cap(cap) {}
  18. };
  19. vector<Edge> G[MAX];
  20. void addEdge(int s, int t, ll cap){
  21.     G[s].pb(Edge(t, sz(G[t]), 0, cap)), G[t].pb(Edge(s, sz(G[s])-1, 0, 0));}
  22. bool dinic_bfs(){
  23.     fill(dist, dist+nodes, -1), dist[src]=0;
  24.     int qt=0; q[qt++]=src;
  25.     for(int qh=0; qh<qt; qh++){
  26.         int u =q[qh];
  27.         forall(e, G[u]){
  28.             int v=e->to;
  29.             if(dist[v]<0 && e->f < e->cap)
  30.                 dist[v]=dist[u]+1, q[qt++]=v;
  31.         }
  32.     }
  33.     return dist[dst]>=0;
  34. }
  35. ll dinic_dfs(int u, ll f){
  36.     if(u==dst) return f;
  37.     for(int &i=work[u]; i<sz(G[u]); i++){
  38.         Edge &e = G[u][i];
  39.         if(e.cap<=e.f) continue;
  40.         int v=e.to;
  41.         if(dist[v]==dist[u]+1){
  42.                 ll df=dinic_dfs(v, min(f, e.cap-e.f));
  43.                 if(df>0){
  44.                         e.f+=df, G[v][e.rev].f-= df;
  45.                         return df;  }
  46.         }
  47.     }
  48.     return 0;
  49. }
  50. ll maxFlow(int _src, int _dst){
  51.     src=_src, dst=_dst;
  52.     ll result=0;
  53.     while(dinic_bfs()){
  54.         fill(work, work+nodes, 0);
  55.         while(ll delta=dinic_dfs(src,INF))
  56.             result+=delta;
  57.     }
  58.     return result; }
  59. int caps[MAX];
  60. int ret[MAX];
  61. long long sum = 0;
  62. vector<tuple<int,int,int> >edges;
  63. int main() {
  64.     ios::sync_with_stdio(false);cin.tie(0);
  65.     nodes = 2050;
  66.     int to, from, m;
  67.     //from 0 ... from, to from ... to + from, src to + from, dst to + from + 1
  68.     cin >> to >> from >> m;
  69.     for (int i = 0, u; i < to; i++) {
  70.         cin >> caps[i];
  71.         sum += caps[i];
  72.     }
  73.     for (int i = 0, u; i < from; i++) {
  74.         cin >> ret[i];
  75.     }
  76.     while (m --) {
  77.         int u, v, t;
  78.         cin >> u >> v >> t;
  79.         u--,v--;
  80.         edges.emplace_back(v, u, t);
  81.     }
  82.     //cout << "END LECTURE " << endl;
  83.     int a = 0, b = 1000001;
  84.     while(b - a > 1) {
  85.         mid = (a + b) >> 1;
  86.         //cout << "@ @ @ " << mid << endl;
  87.        
  88.         for (int i = 0; i < MAX; i++)G[i].clear();
  89.         for (int  i = 0; i < to; i++) {
  90.             //cout << from + i << " " << from + to + 1 << " INT_MAX"<< endl;
  91.             addEdge(from + i, to + from + 1, caps[i]);
  92.         }
  93.         //cout << " ############# " << endl;
  94.         for (int i = 0; i < from; i++) {
  95.             //cout << to + from << " " << i << " "<< ret[i]<< endl;
  96.             addEdge(to + from, i, ret[i]);
  97.         }
  98.         //cout << "EDGES " << endl;
  99.         for (auto edge:edges) {
  100.             int f = get<0>(edge);
  101.             int t = get<1>(edge);
  102.             int time = get<2>(edge);
  103.             if (time <= mid) {
  104.                 //cout << f << " " << t + to << " " << caps[t]<< endl;
  105.                 addEdge(f, t + from, caps[t]);
  106.             }
  107.         }
  108.         ll ans = maxFlow(to + from, to + from + 1);
  109.         //cout << ans << endl;
  110.         if (ans == sum)b = mid;
  111.         else a = mid;
  112.     }
  113.     if (b == 1000001) cout << -1;
  114.     else cout << b << "\n";
  115. }
RAW Paste Data