Download Speed

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

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1005, INF=0x7fffffff;
 
struct Edge {
  int from, to, cap, flow;
 
  Edge(int u, int v, int c, int f) : 
    from(u), to(v), cap(c), flow(f) {}
};
 
vector<vector<int> > ans;
 
struct EK {
  int n, m;             
  vector<Edge> edges;   
  vector<int> G[N];
  int a[N], p[N];  
  // a：点 x -> BFS 过程中最近接近点 x 的边给它的最大流
  // p：点 x -> BFS 过程中最近接近点 x 的边
 
  void init(int n_) {
    n = n_;
    for (int i = 0; i < n; i++) 
        G[i].clear();
    edges.clear();
  }
 
  void AddEdge(int from, int to, int 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);
  }
 
  int Maxflow(int s, int t) {
    int flow = 0;
    while(true) {
      memset(a, 0, sizeof(a));
      queue<int> Q;
      Q.push(s);
      a[s] = INF;
      while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        for (int 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 (int 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()
{
    int n, m;
    cin >> n >> m;
 
    graph.init(n);
    for(int i=1; i<=m; i++)
    {
        int 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: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: ACCEPTED