Distinct Routes

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=10005, INF=0x3f3f3f3f;

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);
    while(m--)
    {
        int u, v;
        cin >> u >> v;
        graph.AddEdge(u, v, 1);
    }
    cout << graph.Maxflow(1, n) << endl;

    // Route
    for(auto x:graph.G[1])
    {
        if(graph.edges[x].flow != 1) continue;
        
        vector<int> ans;
        ans.push_back(1);

        for(int u = graph.edges[x].to; u!=n;)
        {
            ans.push_back(u);
            for(auto e: graph.G[u])
            {
                if(e <=0 || e >= graph.m)
                    continue;
                Edge& edge = graph.edges[e];
                if(edge.flow == 1)
                    u = edge.to;
            }
        }
        ans.push_back(n);
        cout << ans.size() << endl;
        for(auto x: ans)
            cout << x << " ";
        putchar('\n');
    }

    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: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: ACCEPTED