Airport

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 100;
ll W[N*2][N*2];
vector<int> V[N*2];
int n, m;
bool Z[N*2];

ll dfs(int i, ll c, ll w0) {
  if (i == N+n-1) {
    return w0;
  }
  if (Z[i]) return 0;
  Z[i] = 1;
  for (int j : V[i]) {
    ll w = W[i][j];
    if (w >= c) {
      ll v = dfs(j,c,min(w0,w));
      if (v) {
        W[i][j] -= v;
        W[j][i] += v;
        return v;
      }
    }
  }
  return 0;
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> W[i][i+N];
    if (W[i][i+N] == -1) {
      W[i][i+N] = 1e18;
    }
    V[i].push_back(i+N);
  }
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    V[N+a-1].push_back(b-1);
    V[b-1].push_back(N+a-1);
    W[N+a-1][b-1] = 1e18;
  }
  ll ans = 0;
  for (ll c = 1e18; c >= 1; c /= 2) {
    while (1) {
      memset(Z,0,sizeof(Z));
      ll w = dfs(0,c,1e18);
      if (w == 0) break;
      ans += w;
    }
  }
  cout << ans << '\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED