Download Speed

input/code.cpp: In member function 'LL EK::Maxflow(LL, LL)':
input/code.cpp:49: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]
   49 |         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(n);
    for(LL i=1; i<=m; i++)
    {
        LL a, b, c;
        cin >> a >> b >> c;
        graph.AddEdge(a, b, c);
    }

    cout << graph.Maxflow(1, 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