Distinct Routes

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 501;
const int INF = 1e9;

int capacity[MAXN][MAXN];  // Capacity for each teleporter
int parent[MAXN];          // To reconstruct the path
vector<int> adj[MAXN];     // Adjacency list for the graph

// BFS function to find an augmenting path and calculate the flow
int bfs(int n) {
    memset(parent, -1, sizeof(parent));
    parent[1] = -2;  // Start from room 1
    queue<pair<int, int>> q;
    q.push({1, INF});

    while (!q.empty()) {
        int u = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int v : adj[u]) {
            if (parent[v] == -1 && capacity[u][v]) {  // If v is not yet visited and there is capacity
                parent[v] = u;
                int new_flow = min(flow, capacity[u][v]);
                if (v == n) {
                    return new_flow;  // Found an augmenting path to room n
                }
                q.push({v, new_flow});
            }
        }
    }

    return 0;  // No augmenting path found
}

// Edmonds-Karp algorithm to compute the maximum flow
int maxflow(int n) {
    int flow = 0, new_flow;

    while ((new_flow = bfs(n))) {
        flow += new_flow;
        int u = n;

        // Update the capacities along the path
        while (u != 1) {
            int p = parent[u];
            capacity[p][u] -= new_flow;
            capacity[u][p] += new_flow;
            u = p;
        }
    }

    return flow;
}

// Function to find the actual paths based on residual capacities
void find_paths(int n, int m) {
    vector<vector<int>> paths;
    while (true) {
        vector<int> path;
        int u = 1;
        while (u != n) {
            bool found = false;
            for (int v : adj[u]) {
                if (capacity[u][v] == 0 && capacity[v][u] == 1) {  // Residual capacity indicates part of the path
                    path.push_back(u);
                    capacity[v][u] = 0;  // Remove this edge from the path
                    u = v;
                    found = true;
                    break;
                }
            }
            if (!found) break;
        }
        path.push_back(n);
        if (path.size() > 1) {
            paths.push_back(path);
        } else {
            break;
        }
    }

    // Output the results
    cout << paths.size() << endl;
    for (const auto &p : paths) {
        cout << p.size() << endl;
        for (int room : p) {
            cout << room << " ";
        }
        cout << endl;
    }
}

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

    // Initialize the capacity and adjacency list
    memset(capacity, 0, sizeof(capacity));
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);  // Add reverse edge for the residual graph
        capacity[a][b] = 1;   // Each teleporter has a capacity of 1 (can be used once)
    }

    // Find the maximum flow (number of edge-disjoint paths)
    maxflow(n);

    // Find and output the paths
    find_paths(n, m);

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

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER