Airport

input/code.cpp: In member function 'LL EK::Maxflow(LL, LL)':
input/code.cpp:48:26: warning: comparison of integer expressions of different signedness: 'LL' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (LL i = 0; i < G[x].size(); i++) {
      |                        ~~^~~~~~~~~~~~~

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1005, INF=0x7ffffffffffffff;

struct Edge {
  LL from, to, cap, flow;

  Edge(LL u, LL v, LL c, LL f) : 
    from(u), to(v), cap(c), flow(f) {}
};

vector<vector<LL> > ans;

struct EK {
  LL n, m;             
  vector<Edge> edges;   
  vector<LL> G[N];
  LL a[N], p[N];  
  // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
  // p：点 x -> BFS 过程中最近接近点 x 的边

  void init(LL n_) {
    n = n_;
    for (LL i = 0; i < n; i++) 
        G[i].clear();
    edges.clear();
  }

  void AddEdge(LL from, LL to, LL cap) {
    edges.push_back(Edge(from, to, cap, 0));
    edges.push_back(Edge(to, from, 0, 0));
    m = edges.size();
    G[from].push_back(m - 2);
    G[to].push_back(m - 1);
  }

  LL Maxflow(LL s, LL t) {
    LL flow = 0;
    while(true) {
      memset(a, 0, sizeof(a));
      queue<LL> Q;
      Q.push(s);
      a[s] = INF;
      while (!Q.empty()) {
        LL x = Q.front();
        Q.pop();
        for (LL i = 0; i < G[x].size(); i++) {  
          // 遍历以 x 作为起点的边
          Edge& e = edges[G[x][i]];
          if (!a[e.to] && e.cap > e.flow) {
            // G[x][i] 是最近接近点 e.to 的边
            p[e.to] = G[x][i];  
            // 最近接近点 e.to 的边赋给它的流
            a[e.to] = min(a[x], e.cap - e.flow); 
            Q.push(e.to);
          }
        }
        if (a[t]) break;  
      }
      // 如果汇点没有接受到流，说明源点和汇点不在同一个连通分量上
      if (!a[t]) break;
      for (LL u = t; u != s; u = edges[p[u]].from) {  
        // 通过 u 追寻 BFS 过程中 s -> t 的路径
        edges[p[u]].flow += a[t];      
        edges[p[u] ^ 1].flow -= a[t];
      }
      flow += a[t];
    }
    return flow;
  }
}graph;


int main()
{
    LL n, m;
    cin >> n >> m;

    graph.init(2*n);
    for(LL i=1; i<=n; i++)
    {
        LL x;
        cin >> x;
        if(x == -1)
            x = INF;
        graph.AddEdge(i, i+n, x);
    }
    // n -> n-in
    // n+n -> n-out

    while(m--)
    {
        LL u, v;
        cin >> u >> v;
        graph.AddEdge(u+n, v, INF);
    }
    cout << graph.Maxflow(1, n+n) << endl;

    return 0;
}

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