Bài viết này giới thiệu về các thuật toán luồng mạng cơ bản và cách áp dụng chúng để giải quyết nhiều loại bài toán phức tạp. Hai thuật toán chính được trình bày là thuật toán Dinic cho bài toán luồng cực đại (Maximum Flow) và thuật toán Min-Cost Max-Flow dựa trên SPFA.

Thuật Toán Luồng Cực Đại (Maximum Flow) với Dinic

Thuật toán Dinic là một trong những thuật toán hiệu quả nhất để tìm luồng cực đại trong một mạng. Nó hoạt động bằng cách xây dựng các đồ thị tầng (level graph) và sau đó tìm các đường tăng luồng trên đồ thị này bằng cách sử dụng DFS. Các bước chính bao gồm:

1. Sử dụng BFS để xây dựng đồ thị tầng từ nút nguồn đến nút đích. Mỗi nút được gán một mức (level) dựa trên khoảng cách ngắn nhất từ nguồn.
2. Nếu không thể đạt được nút đích từ nguồn, không còn đường tăng luồng nào và thuật toán kết thúc.
3. Sử dụng DFS để tìm các đường tăng luồng từ nguồn đến đích trên đồ thị tầng. Trong quá trình DFS, chỉ cho phép di chuyển đến các nút có mức cao hơn.
4. Thực hiện nhiều lần bước 1 và 2 cho đến khi không thể tìm thấy đường tăng luồng nào nữa.

Mã Nguồn C++: Luồng Cực Đại (Dinic)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

const long long INFINITY_CAP = 1e16 + 7;
const int MAX_NODES = 1e5 + 5;

struct Edge {
    int to_node;
    long long capacity;
    int reverse_edge_idx; // Index of the reverse edge in adj[to_node]
};

std::vector<Edge> adjacency_list[MAX_NODES];
int node_levels[MAX_NODES];
int current_edge_ptr[MAX_NODES]; // For optimization in DFS

int num_nodes, num_edges, source_node, sink_node;

void add_directed_edge(int u, int v, long long cap) {
    adjacency_list[u].push_back({v, cap, (int)adjacency_list[v].size()});
    adjacency_list[v].push_back({u, 0, (int)adjacency_list[u].size() - 1}); // Residual edge with 0 capacity
}

bool build_level_graph() {
    std::fill(node_levels, node_levels + num_nodes + 1, 0);
    std::queue<int> node_queue;

    node_levels[source_node] = 1;
    node_queue.push(source_node);

    while (!node_queue.empty()) {
        int current_node = node_queue.front();
        node_queue.pop();

        for (const auto& edge : adjacency_list[current_node]) {
            if (edge.capacity > 0 && node_levels[edge.to_node] == 0) {
                node_levels[edge.to_node] = node_levels[current_node] + 1;
                node_queue.push(edge.to_node);
                if (edge.to_node == sink_node) return true; // Sink reached
            }
        }
    }
    return false; // Sink not reachable
}

long long send_flow_dfs(int u, long long flow_limit) {
    if (u == sink_node) return flow_limit;

    long long pushed_flow = 0;
    // Iterate from current_edge_ptr to optimize repeated DFS calls
    for (int& i = current_edge_ptr[u]; i < adjacency_list[u].size(); ++i) {
        Edge& current_edge = adjacency_list[u][i];
        if (current_edge.capacity > 0 && node_levels[current_edge.to_node] == node_levels[u] + 1) {
            long long delta_flow = send_flow_dfs(current_edge.to_node, std::min(flow_limit - pushed_flow, current_edge.capacity));
            if (delta_flow == 0) { // If no flow can be pushed through this path
                node_levels[current_edge.to_node] = 0; // Mark as unvisited for next BFS (optimization)
                continue;
            }
            current_edge.capacity -= delta_flow;
            adjacency_list[current_edge.to_node][current_edge.reverse_edge_idx].capacity += delta_flow;
            pushed_flow += delta_flow;
            if (pushed_flow == flow_limit) break; // All required flow pushed
        }
    }
    return pushed_flow;
}

long long calculate_max_flow() {
    long long total_flow = 0;
    while (build_level_graph()) {
        std::fill(current_edge_ptr, current_edge_ptr + num_nodes + 1, 0);
        total_flow += send_flow_dfs(source_node, INFINITY_CAP);
    }
    return total_flow;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_nodes >> num_edges >> source_node >> sink_node;

    for (int i = 0; i < num_edges; ++i) {
        int u, v;
        long long w;
        std::cin >> u >> v >> w;
        add_directed_edge(u, v, w);
    }

    std::cout <> calculate_max_flow() << std::endl;

    return 0;
}

Thuật Toán Min-Cost Max-Flow (Chi Phí Cực Tiểu, Luồng Cực Đại)

Bài toán Min-Cost Max-Flow tìm luồng cực đại trong mạng đồng thời đảm bảo tổng chi phí để vận chuyển luồng đó là nhỏ nhất. Thuật toán thường sử dụng sự kết hợp giữa thuật toán tìm đường tăng luồng (như Ford-Fulkerson hoặc Dinic) và thuật toán tìm đường đi ngắn nhất (như SPFA hoặc Dijkstra với potential) để tìm đường tăng luồng có chi phí nhỏ nhất.

Các bước chính (dựa trên SPFA):

1. Tìm một đường đi từ nguồn đến đích trong đồ thị còn lại có tổng chi phí nhỏ nhất. Thuật toán SPFA (Shortest Path Faster Algorithm) thường được sử dụng cho bước này, vì đồ thị có thể có cạnh với chi phí âm trong đồ thị đối ngẫu.
2. Nếu không tìm thấy đường đi nào (tức là đích không thể đạt được từ nguồn), thuật toán kết thúc.
3. Tính lượng luồng tối đa có thể đẩy qua đường đi ngắn nhất này và cập nhật luồng cũng như chi phí tương ứng.
4. Lặp lại các bước trên cho đến khi không thể tìm thấy đường đi có chi phí dương hoặc không còn đường đi nào.

Mã Nguồn C++: Min-Cost Max-Flow (SPFA)

#include <iostream>
#include <vector>
#lt;queue>
#lt;algorithm>
#lt;limits> // For numeric_limits

const long long INF_LL = std::numeric_limits<long long>::max();
const int MAX_NODES_MCMF = 5005;

struct MCMF_Edge {
    int target_node;
    long long flow_capacity;
    long long edge_cost;
    int reverse_index;
};

std::vector<MCMF_Edge> mcmf_adj[MAX_NODES_MCMF];
long long min_cost_dist[MAX_NODES_MCMF];
int path_edge_indices[MAX_NODES_MCMF]; // Store index of edge in adj[parent]
int path_parent_nodes[MAX_NODES_MCMF]; // Store parent node in shortest path
bool in_queue[MAX_NODES_MCMF]; // For SPFA

int N_mcmf, M_mcmf, S_mcmf, T_mcmf;
long long total_max_flow = 0;
long long total_min_cost = 0;

void add_mcmf_edge(int u, int v, long long capacity, long long cost) {
    mcmf_adj[u].push_back({v, capacity, cost, (int)mcmf_adj[v].size()});
    mcmf_adj[v].push_back({u, 0, -cost, (int)mcmf_adj[u].size() - 1}); // Residual edge with negative cost
}

bool spfa_shortest_path() {
    std::fill(min_cost_dist, min_cost_dist + N_mcmf + 1, INF_LL);
    std::fill(in_queue, in_queue + N_mcmf + 1, false);
    std::queue<int> q_spfa;

    min_cost_dist[S_mcmf] = 0;
    q_spfa.push(S_mcmf);
    in_queue[S_mcmf] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        in_queue[u] = false;

        for (int i = 0; i < mcmf_adj[u].size(); ++i) {
            MCMF_Edge& edge = mcmf_adj[u][i];
            if (edge.flow_capacity > 0 && min_cost_dist[edge.target_node] > min_cost_dist[u] + edge.edge_cost) {
                min_cost_dist[edge.target_node] = min_cost_dist[u] + edge.edge_cost;
                path_parent_nodes[edge.target_node] = u;
                path_edge_indices[edge.target_node] = i; // Store index of this edge in mcmf_adj[u]

                if (!in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return min_cost_dist[T_mcmf] != INF_LL; // Return true if sink is reachable
}

void find_min_cost_max_flow() {
    while (spfa_shortest_path()) {
        long long current_path_flow = INF_LL;

        // Find bottleneck capacity along the shortest path
        for (int v = T_mcmf; v != S_mcmf; v = path_parent_nodes[v]) {
            int u = path_parent_nodes[v];
            int edge_idx = path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, mcmf_adj[u][edge_idx].flow_capacity);
        }

        // Update flow and cost
        total_max_flow += current_path_flow;
        total_min_cost += current_path_flow * min_cost_dist[T_mcmf];

        // Update capacities in residual graph
        for (int v = T_mcmf; v != S_mcmf; v = path_parent_nodes[v]) {
            int u = path_parent_nodes[v];
            int edge_idx = path_edge_indices[v];
            mcmf_adj[u][edge_idx].flow_capacity -= current_path_flow;
            mcmf_adj[v][mcmf_adj[u][edge_idx].reverse_index].flow_capacity += current_path_flow;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> N_mcmf >> M_mcmf >> S_mcmf >> T_mcmf;

    for (int i = 0; i < M_mcmf; ++i) {
        int u, v;
        long long capacity, cost;
        std::cin >> u >> v >> capacity >> cost;
        add_mcmf_edge(u, v, capacity, cost);
    }

    find_min_cost_max_flow();
    std::cout <> total_max_flow << " " << total_min_cost << std::endl;

    return 0;
}

Bài Toán Lập Kế Hoạch Khăn Ăn

Bài toán này có thể mô hình hóa bằng Min-Cost Max-Flow. Ý tưởng là chia mỗi ngày thành hai nút: một nút đại diện cho khăn ăn sạch vào ban ngày và một nút đại diện cho khăn ăn bẩn vào buổi tối.

• Từ nguồn (Source) đến nút khăn bẩn của ngày i: dung lượng bằng số khăn bẩn cần dùng r_i, chi phí 0.
• Từ nút khăn sạch của ngày i đến đích (Sink): dung lượng bằng số khăn bẩn cần dùng r_i, chi phí 0.
• Từ nguồn đến nút khăn sạch của ngày i: dung lượng vô hạn, chi phí p (giá mua một khăn mới).
• Từ nút khăn bẩn của ngày i đến nút khăn bẩn của ngày i+1: dung lượng vô hạn, chi phí 0 (có thể giữ khăn bẩn qua đêm).
• Từ nút khăn bẩn của ngày i đến nút khăn sạch của ngày i+m (giặt nhanh): dung lượng vô hạn, chi phí f.
• Từ nút khăn bẩn của ngày i đến nút khăn sạch của ngày i+n (giặt chậm): dung lượng vô hạn, chi phí s.

Mục tiêu là tìm Min-Cost Max-Flow để đáp ứng nhu cầu khăn ăn với chi phí thấp nhất.

Mã Nguồn C++: Lập Kế Hoạch Khăn Ăn

#include <iostream>
#include <vector>
#include <queue>
#lt;algorithm>
#lt;cstring> // For memset
#lt;limits>

const long long INF_VAL_MCMF = std::numeric_limits<long long>::max() / 2; // Avoid overflow
const int MAX_NAPKIN_NODES = 5005; // Max 2N+1 nodes
const int MAX_NAPKIN_EDGES = 5e5 + 5;

struct NapkinEdge {
    int target;
    int next_edge;
    long long flow;
    long long cost;
};

NapkinEdge edge_list[MAX_NAPKIN_EDGES * 2]; // Store edges and their reverse
int head_idx[MAX_NAPKIN_NODES];
int edge_count = 1;

long long current_dist[MAX_NAPKIN_NODES];
int current_path_ptr[MAX_NAPKIN_NODES];
bool in_spfa_queue[MAX_NAPKIN_NODES];

int num_days, req_napkins[MAX_NAPKIN_NODES];
long long new_napkin_cost, fast_wash_days, fast_wash_cost, slow_wash_days, slow_wash_cost;

int source_node_napkin, sink_node_napkin;
long long total_flow_napkin, total_cost_napkin;

void add_napkin_edge(int u, int v, long long flow_cap, long long edge_cst) {
    edge_list[++edge_count] = {v, head_idx[u], flow_cap, edge_cst}; head_idx[u] = edge_count;
    edge_list[++edge_count] = {u, head_idx[v], 0, -edge_cst}; head_idx[v] = edge_count;
}

bool spfa_for_min_cost() {
    std::fill(current_dist, current_dist + sink_node_napkin + 1, INF_VAL_MCMF);
    std::fill(in_spfa_queue, in_spfa_queue + sink_node_napkin + 1, false);
    std::queue<int> q;

    q.push(source_node_napkin);
    current_dist[source_node_napkin] = 0;
    in_spfa_queue[source_node_napkin] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        in_spfa_queue[u] = false;

        for (int i = head_idx[u]; i; i = edge_list[i].next_edge) {
            int v = edge_list[i].target;
            if (edge_list[i].flow > 0 && current_dist[v] > current_dist[u] + edge_list[i].cost) {
                current_dist[v] = current_dist[u] + edge_list[i].cost;
                current_path_ptr[v] = i; // For path reconstruction in DFS
                if (!in_spfa_queue[v]) {
                    q.push(v);
                    in_spfa_queue[v] = true;
                }
            }
        }
    }
    return current_dist[sink_node_napkin] != INF_VAL_MCMF;
}

long long dfs_find_flow(int u, long long limit_flow) {
    if (u == sink_node_napkin) return limit_flow;
    in_spfa_queue[u] = true; // Mark as visited for this DFS traversal

    long long current_pushed_flow = 0;
    for (int i = head_idx[u]; i; i = edge_list[i].next_edge) {
        int v = edge_list[i].target;
        // Check for remaining capacity, level increase, and not already visited in this DFS
        if (!in_spfa_queue[v] && edge_list[i].flow > 0 && current_dist[v] == current_dist[u] + edge_list[i].cost) {
            long long delta = dfs_find_flow(v, std::min(limit_flow - current_pushed_flow, edge_list[i].flow));
            if (delta == 0) continue;
            edge_list[i].flow -= delta;
            edge_list[i ^ 1].flow += delta;
            current_pushed_flow += delta;
            if (current_pushed_flow == limit_flow) break;
        }
    }
    in_spfa_queue[u] = false; // Unmark for future DFS calls from different paths
    return current_pushed_flow;
}

void solve_napkin_problem() {
    total_flow_napkin = 0;
    total_cost_napkin = 0;
    while (spfa_for_min_cost()) {
        // Need to reset in_spfa_queue for DFS as it's used for visited tracking
        std::fill(in_spfa_queue, in_spfa_queue + sink_node_napkin + 1, false);
        long long flow_found = dfs_find_flow(source_node_napkin, INF_VAL_MCMF);
        total_flow_napkin += flow_found;
        total_cost_napkin += flow_found * current_dist[sink_node_napkin];
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_days;
    for (int i = 1; i <= num_days; ++i) std::cin >> req_napkins[i];
    std::cin >> new_napkin_cost >> fast_wash_days >> fast_wash_cost >> slow_wash_days >> slow_wash_cost;

    source_node_napkin = 0;
    sink_node_napkin = 2 * num_days + 1; // Nodes for day i (clean) and day i+N (dirty)

    // S -> Clean_Day_i (buy new napkins)
    for (int i = 1; i <= num_days; ++i) add_napkin_edge(source_node_napkin, i, INF_VAL_MCMF, new_napkin_cost);
    // Clean_Day_i -> T (satisfy demand)
    for (int i = 1; i <= num_days; ++i) add_napkin_edge(i, sink_node_napkin, req_napkins[i], 0);
    // Dirty_Day_i -> S (new dirty napkins generated)
    for (int i = 1; i <= num_days; ++i) add_napkin_edge(source_node_napkin, i + num_days, req_napkins[i], 0);
    // Dirty_Day_i -> Dirty_Day_(i+1) (keep dirty napkins)
    for (int i = 1; i < num_days; ++i) add_napkin_edge(i + num_days, i + num_days + 1, INF_VAL_MCMF, 0);
    // Dirty_Day_i -> Clean_Day_(i+fast_wash_days) (fast wash)
    for (int i = 1; i + fast_wash_days <= num_days; ++i) add_napkin_edge(i + num_days, i + fast_wash_days, INF_VAL_MCMF, fast_wash_cost);
    // Dirty_Day_i -> Clean_Day_(i+slow_wash_days) (slow wash)
    for (int i = 1; i + slow_wash_days <= num_days; ++i) add_napkin_edge(i + num_days, i + slow_wash_days, INF_VAL_MCMF, slow_wash_cost);

    solve_napkin_problem();
    std::cout <> total_cost_napkin << std::endl;

    return 0;
}

Bài Toán Chuyển Giao Giữa Các Hệ Sao

Bài toán yêu cầu tìm số ngày tối thiểu để chuyển một số lượng người nhất định giữa các điểm trong không gian, sử dụng các tàu vũ trụ có lịch trình xoay vòng. Đây là một bài toán Luồng Cực Đại phân tầng (Layered Max-Flow).

Ý tưởng là tạo ra các tầng cho từng ngày. Mỗi nút trong đồ thị được nhân bản thành T * N nút, với T là số ngày tối đa và N là số vị trí. Các cạnh được thêm vào để mô tả:

• Người ở lại một vị trí: Từ (ngày_t-1, vị_trí_i) đến (ngày_t, vị_trí_i) với dung lượng vô hạn.
• Người di chuyển bằng tàu vũ trụ: Nếu tàu k di chuyển từ vị_trí_u đến vị_trí_v vào ngày t, thêm cạnh từ (ngày_t-1, vị_trí_u) đến (ngày_t, vị_trí_v) với dung lượng bằng sức chứa của tàu h_k.

Chúng ta có thể tăng dần số ngày T, xây dựng đồ thị tương ứng và tính luồng cực đại. Khi luồng cực đại đạt đến số người cần chuyển, đó là số ngày tối thiểu. Cần xử lý đặc biệt cho các nút nguồn (vị trí ban đầu) và đích (vị trí cuối cùng) và các vị trí có lịch trình xoay vòng.

Mã Nguồn C++: Chuyển Giao Giữa Các Hệ Sao

#include <iostream>
#include <vector>
#include <queue>
#lt;cstring> // For memset
#lt;algorithm>

const int INF_FLOW = 1e9 + 7;
const int MAX_TOTAL_NODES = 20005; // Maximum possible nodes (Days * N + other nodes)
const int MAX_SPACESHIPS = 25; // Max m
const int MAX_STATIONS = 15; // Max n

struct SpaceEdge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

SpaceEdge space_edges[MAX_TOTAL_NODES * 10]; // Increased edge capacity
int space_head[MAX_TOTAL_NODES];
int space_edge_counter = 1;

int station_count, ship_count, required_passengers;
int ship_capacity[MAX_SPACESHIPS];
int ship_route_len[MAX_SPACESHIPS];
std::vector<int> ship_route[MAX_SPACESHIPS]; // ship_route[k][day % route_len[k]]

int level_array[MAX_TOTAL_NODES];
int current_dfs_ptr[MAX_TOTAL_NODES];
long long current_max_flow;

// Function to map (day, station_id) to a unique node ID
// Day 0 represents the starting point
inline int get_node_id(int day, int station_id) {
    // If station_id is 0, it means Earth. We need to handle this.
    // For Earth (station 0), we use station_count + 1 to distinguish.
    // However, the problem statement often uses 0 as Earth for route points,
    // and stations 1 to N for regular stations. Let's assume actual stations are 0 to N-1
    // or 1 to N. The original problem defines N stations, usually 1 to N.
    // So if station 0 is Earth, map it differently.
    // Let's assume stations are 0 to N-1 (N distinct places).
    // Original problem uses 0 as earth, nodes 1..N-1 for other stations.
    // If 0 is Earth, we map to 0. If station_id is -1 (for space), it's special.
    // Given the problem's ID usage, it seems stations are 0 to N-1.
    // Let's use station_id 0 to N-1 for N stations.
    // A mapping (t, i) >> t * station_count + i works for 0-indexed stations.
    // If stations are 1-indexed, then t * station_count + station_id.
    // The given problem uses 0 as Earth, and N total stations. So N points are 0,1,...,N-1.
    // The code uses N stations from 1 to N. Ship route v[i][j] gives the station ID.
    // If v[i][j] is -1, it means spaceship is in space, not at a station.
    // If v[i][j] is 0, it means Earth.
    // So the nodes for a given day t are t*N + 1, t*N + 2, ..., t*N + N.
    // Earth is node 0.
    // The problem statement implies N stations, and the spaceship can start at any of them.
    // Let's denote stations as 0 to N-1 for the sake of clarity if 0 is Earth.
    // The provided code uses 1 to N for stations. So '0' is Earth.
    // The `pos` function seems to map station ID to 0..r[i]-1.
    // The `id` function maps to t*n+pos.
    // `pos(t, i)` gets the station number for ship `i` at time `t`.
    // It implies `v[i][t%r[i]]` is the station index.
    // If `v[i][(t-1)%r[i]] == 0`, it means at Earth at day t-1.
    // Let's use 0 for Earth and 1 to `station_count-1` for other stations.
    // The node mapping: `(day * num_stations + station_id)`.
    // Example: (t, 0) for Earth at day t.
    // Original code: `t*n+pos(t,i)`. If stations are 1..N, N nodes.
    // If '0' is Earth, the total stations could be N+1.
    // Let's simplify and follow the structure for node ID directly from the original logic.
    // `id(t,i)` maps to `t*n + pos(t,i)`.
    // `pos(t,i)` means the station ID (0 to N-1 or 1 to N).
    // Let's assume actual stations are 1 to `station_count`.
    // The `pos(t,i)` implies station index `v[i][t%r[i]]`. If `v[i][j] = -1` it means in space.
    // If `v[i][j] = 0` it means earth.
    // This implies nodes from 0 to `station_count`.
    // For simplicity, let's keep the node mapping: `station_count * day + station_index`.
    // Source `S_node` and Sink `T_node` are special.
    // Max Day is 1000. So max nodes = 1000 * 10 + 2 (S, T) approx. 10000+2.
    // The array N=20005 is sufficient.
    // Let's use `station_count` to represent N, `ship_count` to represent M.
    return day * station_count + station_id;
}

void add_space_edge(int u, int v, int cap) {
    space_edges[++space_edge_counter] = {v, space_head[u], cap}; space_head[u] = space_edge_counter;
    space_edges[++space_edge_counter] = {u, space_head[v], 0}; space_head[v] = space_edge_counter;
}

bool bfs_space_flow(int src, int dst) {
    std::fill(level_array, level_array + MAX_TOTAL_NODES, 0);
    std::queue<int> q;
    q.push(src);
    level_array[src] = 1;

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

        for (int i = space_head[u]; i; i = space_edges[i].next_edge_idx) {
            int v = space_edges[i].target_node;
            if (space_edges[i].capacity > 0 && level_array[v] == 0) {
                level_array[v] = level_array[u] + 1;
                q.push(v);
                if (v == dst) return true;
            }
        }
    }
    return false;
}

int dfs_space_flow(int u, int flow_limit, int src, int dst) {
    if (u == dst) return flow_limit;

    int current_flow = 0;
    for (int& i = current_dfs_ptr[u]; i; i = space_edges[i].next_edge_idx) {
        int v = space_edges[i].target_node;
        if (space_edges[i].capacity > 0 && level_array[v] == level_array[u] + 1) {
            int pushed = dfs_space_flow(v, std::min(flow_limit - current_flow, space_edges[i].capacity), src, dst);
            if (pushed == 0) {
                level_array[v] = 0; // Pruning
                continue;
            }
            space_edges[i].capacity -= pushed;
            space_edges[i ^ 1].capacity += pushed;
            current_flow += pushed;
            if (current_flow == flow_limit) break;
        }
    }
    return current_flow;
}

void dinic_space_flow(int src, int dst) {
    while (bfs_space_flow(src, dst)) {
        std::memcpy(current_dfs_ptr, space_head, sizeof(int) * MAX_TOTAL_NODES); // Reset current_dfs_ptr
        current_max_flow += dfs_space_flow(src, INF_FLOW, src, dst);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> station_count >> ship_count >> required_passengers;

    for (int i = 1; i <= ship_count; ++i) {
        std::cin >> ship_capacity[i] >> ship_route_len[i];
        ship_route[i].resize(ship_route_len[i]);
        for (int j = 0; j < ship_route_len[i]; ++j) {
            std::cin >> ship_route[i][j];
            // Adjust station IDs for 0-indexing if necessary.
            // Original code implies 0 is Earth, 1 to N-1 for other stations.
            // If the input gives 1 to N, then use it as is.
            // Let's assume input station_ids are 0 to N-1 (Earth is 0).
        }
    }

    int actual_source = get_node_id(0, 0); // Earth at day 0
    int actual_sink = MAX_TOTAL_NODES - 1; // A global sink for destination

    // Add virtual source for initial passengers at Earth
    int virtual_source_node = MAX_TOTAL_NODES - 2;
    int virtual_sink_node = MAX_TOTAL_NODES - 1;

    // Connect source to Earth at day 0
    add_space_edge(virtual_source_node, get_node_id(0, 0), required_passengers);

    for (int t = 1; t <= 1000; ++t) { // Maximum 1000 days as an upper bound
        // Add edges for people staying at a station
        for (int i = 0; i < station_count; ++i) { // station_count stations from 0 to station_count-1
            add_space_edge(get_node_id(t - 1, i), get_node_id(t, i), INF_FLOW);
        }

        // Add edges for spaceship movements
        for (int i = 1; i <= ship_count; ++i) {
            int prev_station = ship_route[i][(t - 1) % ship_route_len[i]];
            int curr_station = ship_route[i][t % ship_route_len[i]];

            if (prev_station == -1) continue; // Ship in space on previous day

            int u = get_node_id(t - 1, prev_station);
            int v = get_node_id(t, curr_station);

            // Handle special cases for Earth (station 0) and destination (station_count - 1)
            // The problem statement implies station 0 as Earth, and station N-1 as the target.
            // However, the original code uses fixed nodes S, T.
            // The problem uses N stations. If 0 is Earth, then target could be any station N-1.
            // The problem statement talks about 'N' distinct places. If Earth is one of them, then 0..N-1.
            // The target is typically 'N-1' (last station) if it's N places.
            // The original code uses '0' as Earth.
            // Assuming target station is 0 for source, and any specified N-1 for destination.
            // Let's make target station `station_count - 1` (last index if 0-indexed, or `station_count` if 1-indexed)
            // The original code implies station_id 0 to N-1 for N stations.
            // And Earth is station 0. The ultimate destination could be any station.
            // The actual target is 0 for initial passenger start and Earth (0) as the source,
            // and the 'target' node is implicitly station `n-1` or `n` (last station).
            // Let's say the destination is `station_count-1` for now.

            // The original code's `pos` and `id` functions are a bit tricky.
            // `pos(t,i)` means the current station for ship `i` at time `t`.
            // `id(t,i)` is the node index.
            // The problem implies that passengers *start* at Earth (station 0),
            // and want to reach station `n-1` (if 0-indexed) or `n` (if 1-indexed).
            // The destination for passengers seems to be station `n-1` (the last station if numbered 0 to n-1).
            // The actual problem statement needs more clarity on destination.
            // Based on the code, S is (N-1), T is (N-2).
            // If `pos(t,i) == -1` means ship is in space.
            // If `pos(t,i) == 0` means ship is at Earth.
            // The source for passengers is Earth (station 0).
            // The destination for passengers is typically the last station (station_count-1).

            // Let's refine based on original code:
            // S_node: MAX_TOTAL_NODES - 2
            // T_node: MAX_TOTAL_NODES - 1
            // `pos(t,i)` gives the station index for ship i at day t.
            // If `pos(t,i)` is 0 (Earth):
            //   - If `pos(t-1, i)` was 0: ship stayed at Earth. No special edge needed as `(t-1)*n + 0` to `t*n + 0` is covered by 'stay'
            //   - If `pos(t-1, i)` was another station `j`: `(t-1)*n + j` to `t*n + 0`.
            // The `id` function maps `(day, station_index)` to `day * n + station_index`.
            // This suggests 0-indexed stations (0 to n-1).
            // So, source node is `0` (Earth) at day 0. Target node is `station_count-1` (last station).

            // Edges for passengers moving via spaceship:
            if (prev_station != -1 && curr_station != -1) { // Ship must be at a station on both days
                if (prev_station == 0) u = virtual_source_node; // Passengers start at Earth (station 0)
                else u = get_node_id(t - 1, prev_station);

                if (curr_station == 0) add_space_edge(u, get_node_id(t, 0), ship_capacity[i]);
                else if (curr_station == station_count - 1) add_space_edge(u, virtual_sink_node, ship_capacity[i]); // Destination is last station
                else add_space_edge(u, get_node_id(t, curr_station), ship_capacity[i]);
            }
        }
        
        // Connect station (station_count - 1) at day t to final sink_node for passengers that reached destination
        add_space_edge(get_node_id(t, station_count - 1), virtual_sink_node, INF_FLOW); // Any passenger reaching last station can leave

        current_max_flow = 0; // Reset flow for each day
        dinic_space_flow(virtual_source_node, virtual_sink_node);

        if (current_max_flow >= required_passengers) {
            std::cout <> t << std::endl;
            return 0;
        }
    }

    std::cout <> 0 << std::endl; // No solution within the maximum days
    return 0;
}

Bài Toán Ghép Cặp Phi Công

Bài toán này là một ví dụ kinh điển về ghép cặp lưỡng phân (bipartite matching) và có thể được giải quyết bằng thuật toán luồng cực đại. Ta có hai nhóm phi công: phi công nước ngoài và phi công Anh. Mỗi phi công nước ngoài có thể lái một số loại máy bay, và mỗi loại máy bay cần một phi công Anh.

Mô hình đồ thị:

• Tạo một nút nguồn S và một nút đích T.
• Đối với mỗi phi công nước ngoài i, thêm một cạnh từ S đến i với dung lượng 1.
• Đối với mỗi phi công Anh j, thêm một cạnh từ j đến T với dung lượng 1.
• Nếu phi công nước ngoài i có thể làm việc với phi công Anh j (hoặc lái loại máy bay mà phi công Anh j cần), thêm một cạnh từ i đến j với dung lượng 1.

Luồng cực đại trong mạng này sẽ là số cặp phi công tối đa có thể ghép được. Để in ra các cặp, ta kiểm tra các cạnh từ phi công nước ngoài đến phi công Anh có luồng bằng 1 trong đồ thị đối ngẫu.

Mã Nguồn C++: Ghép Cặp Phi Công

#include <iostream>
#include <vector>
#include <queue>
#lt;cstring> // For memset
#lt;algorithm>

const int MAX_PILOT_NODES = 305;
const int INFINITY_PILOT_FLOW = 1e9 + 7;

struct PilotEdge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

PilotEdge pilot_edges[MAX_PILOT_NODES * MAX_PILOT_NODES * 2]; // Max N*N edges
int pilot_head[MAX_PILOT_NODES];
int pilot_edge_counter = 1;

int num_foreign_pilots, num_british_pilots_total; // m and n from problem
int pilot_source, pilot_sink;

int pilot_level[MAX_PILOT_NODES];
int pilot_current_ptr[MAX_PILOT_NODES];
long long pilot_total_flow_res;

void add_pilot_edge(int u, int v, int cap) {
    pilot_edges[++pilot_edge_counter] = {v, pilot_head[u], cap}; pilot_head[u] = pilot_edge_counter;
    pilot_edges[++pilot_edge_counter] = {u, pilot_head[v], 0}; pilot_head[v] = pilot_edge_counter;
}

bool bfs_pilot_flow() {
    std::fill(pilot_level, pilot_level + num_british_pilots_total + 2, 0); // Max node n+1
    std::queue<int> q;
    q.push(pilot_source);
    pilot_level[pilot_source] = 1;

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

        for (int i = pilot_head[u]; i; i = pilot_edges[i].next_edge_idx) {
            int v = pilot_edges[i].target_node;
            if (pilot_edges[i].capacity > 0 && pilot_level[v] == 0) {
                pilot_level[v] = pilot_level[u] + 1;
                q.push(v);
                if (v == pilot_sink) return true;
            }
        }
    }
    return false;
}

int dfs_pilot_flow(int u, int flow_limit) {
    if (u == pilot_sink) return flow_limit;

    int current_pushed = 0;
    for (int& i = pilot_current_ptr[u]; i; i = pilot_edges[i].next_edge_idx) {
        int v = pilot_edges[i].target_node;
        if (pilot_edges[i].capacity > 0 && pilot_level[v] == pilot_level[u] + 1) {
            int pushed = dfs_pilot_flow(v, std::min(flow_limit - current_pushed, pilot_edges[i].capacity));
            if (pushed == 0) {
                pilot_level[v] = 0; // Pruning
                continue;
            }
            pilot_edges[i].capacity -= pushed;
            pilot_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void dinic_solve_pilot() {
    while (bfs_pilot_flow()) {
        std::memcpy(pilot_current_ptr, pilot_head, sizeof(int) * (num_british_pilots_total + 2));
        pilot_total_flow_res += dfs_pilot_flow(pilot_source, INFINITY_PILOT_FLOW);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_foreign_pilots >> num_british_pilots_total;

    std::vector<std::pair<int, int>> initial_pairs; // To store original edges for output

    while (true) {
        int foreign_idx, british_idx;
        std::cin >> foreign_idx >> british_idx;
        if (foreign_idx == -1 && british_idx == -1) break;
        add_pilot_edge(foreign_idx, british_idx, 1);
        initial_pairs.push_back({foreign_idx, british_idx});
    }

    pilot_source = 0;
    pilot_sink = num_british_pilots_total + 1; // max node ID is num_british_pilots_total

    // Add edges from source to foreign pilots
    for (int i = 1; i <= num_foreign_pilots; ++i) add_pilot_edge(pilot_source, i, 1);
    // Add edges from British pilots to sink
    for (int i = num_foreign_pilots + 1; i <= num_british_pilots_total; ++i) add_pilot_edge(i, pilot_sink, 1);

    dinic_solve_pilot();
    std::cout <> pilot_total_flow_res << '\n';

    // Output the matching pairs
    for (const auto& pair : initial_pairs) {
        int u = pair.first;
        int v = pair.second;
        // Check if the edge (u, v) has residual capacity 0 and (v, u) has capacity 1
        // This means flow has passed from u to v
        for (int i = pilot_head[u]; i; i = pilot_edges[i].next_edge_idx) {
            if (pilot_edges[i].target_node == v && pilot_edges[i].capacity == 0) {
                std::cout <> u << " " << v << '\n';
                break;
            }
        }
    }

    return 0;
}

Bài Toán Vá Lỗi Phần Mềm

Đây là một bài toán đường đi ngắn nhất (shortest path) trên đồ thị trạng thái, thường được giải bằng Dijkstra hoặc SPFA, không phải là một bài toán luồng mạng trực tiếp. Mỗi trạng thái của hệ thống (được biểu diễn bằng một mặt nạ bit) là một nút trong đồ thị. Các bản vá lỗi tạo thành các cạnh giữa các trạng thái.

• Mỗi trạng thái là một số nguyên mask (mặt nạ bit) từ 0 đến 2^N - 1, với N là số lỗi. Bit thứ j của mask là 1 nếu lỗi j tồn tại, 0 nếu đã được sửa.
• Trạng thái ban đầu là tất cả các lỗi đều tồn tại ((1 << N) - 1). Trạng thái đích là không có lỗi nào (0).
• Mỗi bản vá lỗi k có chi phí val_k và ảnh hưởng đến các lỗi: yêu cầu lỗi b1_k phải có, lỗi b2_k không được có, sau khi áp dụng lỗi f1_k được sửa, lỗi f2_k xuất hiện.
• Nếu một bản vá lỗi có thể áp dụng cho trạng thái hiện tại p, nó sẽ tạo ra một trạng thái mới to. Thêm cạnh từ p đến to với trọng số val_k.

Sử dụng thuật toán Dijkstra (với hàng đợi ưu tiên) để tìm đường đi ngắn nhất từ trạng thái ban đầu đến trạng thái đích.

Mã Nguồn C++: Vá Lỗi Phần Mềm

#include <iostream>
#include <vector>
#include <string>
#lt;queue>
#lt;algorithm>
#lt;limits> // For numeric_limits

const int MAX_PATCH_PROBLEMS = 21; // Max N
const int MAX_PATCHES = 105; // Max M
const int MAX_STATE_SPACE = 1 << MAX_PATCH_PROBLEMS; // 2^N states

struct PatchInfo {
    int cost;
    int required_bits_on; // b1
    int required_bits_off; // b2
    int fixed_bits; // f1
    int introduced_bits; // f2
};

struct StateNode {
    int state_mask;
    int current_cost;

    // Custom comparator for priority queue (min-heap)
    bool operator<(const StateNode& other) const {
        return current_cost > other.current_cost;
    }
};

PatchInfo all_patches[MAX_PATCHES];
int min_costs[MAX_STATE_SPACE];
bool visited_states[MAX_STATE_SPACE];

int num_errors, num_patches;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_errors >> num_patches;

    for (int i = 1; i <= num_patches; ++i) {
        std::string s_required, s_effect;
        std::cin >> all_patches[i].cost >> s_required >> s_effect;

        for (int j = 0; j < num_errors; ++j) {
            if (s_required[j] == '+') all_patches[i].required_bits_on |= (1 << j);
            if (s_required[j] == '-') all_patches[i].required_bits_off |= (1 << j);
            if (s_effect[j] == '+') all_patches[i].introduced_bits |= (1 << j);
            if (s_effect[j] == '-') all_patches[i].fixed_bits |= (1 << j);
        }
    }

    std::fill(min_costs, min_costs + (1 << num_errors), std::numeric_limits<int>::max());
    std::priority_queue<StateNode> pq;

    int initial_state = (1 << num_errors) - 1; // All errors exist
    min_costs[initial_state] = 0;
    pq.push({initial_state, 0});

    while (!pq.empty()) {
        StateNode current = pq.top();
        pq.pop();

        int u_state = current.state_mask;
        int u_cost = current.current_cost;

        if (visited_states[u_state]) continue;
        visited_states[u_state] = true;

        if (u_state == 0) { // All errors fixed
            std::cout <> u_cost << std::endl;
            return 0;
        }

        for (int i = 1; i <= num_patches; ++i) {
            // Check if patch 'i' can be applied to u_state
            if (((u_state | all_patches[i].required_bits_on) != u_state) || // Missing required errors
                ((u_state & all_patches[i].required_bits_off) != 0)) {      // Has forbidden errors
                continue;
            }

            // Calculate the new state after applying patch 'i'
            int next_state = u_state;
            next_state = (next_state | all_patches[i].introduced_bits); // Add new errors
            next_state = (next_state & (~all_patches[i].fixed_bits));   // Remove fixed errors

            if (min_costs[next_state] > u_cost + all_patches[i].cost) {
                min_costs[next_state] = u_cost + all_patches[i].cost;
                pq.push({next_state, min_costs[next_state]});
            }
        }
    }

    std::cout <> 0 << std::endl; // Should not happen if a solution exists
    return 0;
}

Bài Toán Kế Hoạch Bay Vào Không Gian

Bài toán này yêu cầu tìm một tập hợp các nhiệm vụ có trọng số lớn nhất sao cho nếu một nhiệm vụ được chọn, tất cả các điều kiện tiên quyết của nó cũng phải được chọn. Đây là bài toán đồ thị bao đóng có trọng số cực đại (Maximum Weight Closure), có thể giải bằng cách chuyển đổi sang bài toán Min-Cut (cắt cực tiểu).

Mô hình đồ thị:

• Tạo một nút nguồn S và một nút đích T.
• Đối với mỗi nhiệm vụ i có trọng số dương P_i, thêm một cạnh từ S đến i với dung lượng P_i.
• Đối với mỗi tài nguyên j có chi phí âm (hoặc trọng số dương -C_j), thêm một cạnh từ j đến T với dung lượng -C_j.
• Đối với mỗi phụ thuộc: nếu nhiệm vụ i yêu cầu tài nguyên j, thêm một cạnh từ i đến j với dung lượng vô hạn.
• Các nút có trọng số 0 không cần kết nối đặc biệt.

Tổng trọng số của bao đóng cực đại bằng tổng trọng số dương của tất cả các nút trừ đi giá trị của Min-Cut. Các nút thuộc phía nguồn sau khi cắt cực tiểu sẽ tạo thành bao đóng cực đại. Cụ thể, các nút mà vẫn còn kết nối với nguồn trong đồ thị đối ngẫu (tức là có level[node] > 0 trong Dinic sau khi chạy BFS cuối cùng) là một phần của bao đóng.

Mã Nguồn C++: Kế Hoạch Bay Vào Không Gian

#include <iostream>
#include <vector>
#include <string>
#lt;sstream> // For istringstream
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const long long INF_CAP_MWC = std::numeric_limits<long long>::max() / 2; // Avoid overflow
const int MAX_NODES_MWC = 505; // N experiments + M resources + S + T

struct MWC_Edge {
    int target;
    int next_edge_idx;
    long long capacity;
};

MWC_Edge mwc_edges[MAX_NODES_MWC * MAX_NODES_MWC * 2]; // Max N*N edges
int mwc_head[MAX_NODES_MWC];
int mwc_edge_counter = 1;

int num_experiments, num_resources;
int experiment_profits[MAX_NODES_MWC];
int resource_costs[MAX_NODES_MWC];

int mwc_source, mwc_sink;

int mwc_node_levels[MAX_NODES_MWC];
int mwc_current_ptr[MAX_NODES_MWC];
long long mwc_max_flow_result;

void add_mwc_edge(int u, int v, long long cap) {
    mwc_edges[++mwc_edge_counter] = {v, mwc_head[u], cap}; mwc_head[u] = mwc_edge_counter;
    mwc_edges[++mwc_edge_counter] = {u, mwc_head[v], 0}; mwc_head[v] = mwc_edge_counter;
}

bool bfs_mwc_flow() {
    std::fill(mwc_node_levels, mwc_node_levels + mwc_sink + 1, 0);
    std::queue<int> q;
    q.push(mwc_source);
    mwc_node_levels[mwc_source] = 1;

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

        for (int i = mwc_head[u]; i; i = mwc_edges[i].next_edge_idx) {
            int v = mwc_edges[i].target;
            if (mwc_edges[i].capacity > 0 && mwc_node_levels[v] == 0) {
                mwc_node_levels[v] = mwc_node_levels[u] + 1;
                q.push(v);
                if (v == mwc_sink) return true;
            }
        }
    }
    return false;
}

long long dfs_mwc_flow(int u, long long flow_limit) {
    if (u == mwc_sink) return flow_limit;

    long long current_pushed = 0;
    for (int& i = mwc_current_ptr[u]; i; i = mwc_edges[i].next_edge_idx) {
        int v = mwc_edges[i].target;
        if (mwc_edges[i].capacity > 0 && mwc_node_levels[v] == mwc_node_levels[u] + 1) {
            long long pushed = dfs_mwc_flow(v, std::min(flow_limit - current_pushed, mwc_edges[i].capacity));
            if (pushed == 0) {
                mwc_node_levels[v] = 0; // Pruning
                continue;
            }
            mwc_edges[i].capacity -= pushed;
            mwc_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void solve_mwc_problem() {
    while (bfs_mwc_flow()) {
        std::fill(mwc_current_ptr, mwc_current_ptr + mwc_sink + 1, 0); // Reset for each DFS phase
        std::memcpy(mwc_current_ptr, mwc_head, sizeof(int) * (mwc_sink + 1));
        mwc_max_flow_result += dfs_mwc_flow(mwc_source, INF_CAP_MWC);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_experiments >> num_resources;

    mwc_source = 0;
    mwc_sink = num_experiments + num_resources + 1;
    long long total_positive_profit = 0;

    // Experiments are nodes 1 to num_experiments
    // Resources are nodes num_experiments+1 to num_experiments+num_resources
    for (int i = 1; i <= num_experiments; ++i) {
        std::string line_buffer;
        std::cin >> std::ws; // Consume leading whitespace
        std::getline(std::cin, line_buffer);
        std::istringstream iss(line_buffer);

        iss >> experiment_profits[i];
        if (experiment_profits[i] > 0) {
            add_mwc_edge(mwc_source, i, experiment_profits[i]);
            total_positive_profit += experiment_profits[i];
        } else {
            // Negative profit experiments can be ignored or handled by min-cost max-flow (not min-cut)
            // Or add edge from experiment to source with capacity -profit
        }

        int required_resource_idx;
        while (iss >> required_resource_idx) {
            // Edge from experiment to resource (experiment i requires resource j)
            add_mwc_edge(i, num_experiments + required_resource_idx, INF_CAP_MWC);
        }
    }

    for (int i = 1; i <= num_resources; ++i) {
        std::cin >> resource_costs[i];
        // Edge from resource to sink (cost of resource j)
        add_mwc_edge(num_experiments + i, mwc_sink, resource_costs[i]);
    }

    solve_mwc_problem();

    // Output selected experiments
    for (int i = 1; i <= num_experiments; ++i) {
        if (mwc_node_levels[i] != 0) { // If node i is reachable from source in residual graph (part of S-side of min cut)
            std::cout <> i << " ";
        }
    }
    std::cout << '\n';

    // Output selected resources
    for (int i = 1; i <= num_resources; ++i) {
        if (mwc_node_levels[num_experiments + i] != 0) { // If node num_experiments + i is reachable
            std::cout <> i << " ";
        }
    }
    std::cout << '\n';

    // Max Weight Closure = Sum of positive profits - Min Cut
    std::cout <> total_positive_profit - mwc_max_flow_result << '\n';

    return 0;
}

Bài Toán Ngân Hàng Đề Thi

Bài toán này có thể được mô hình hóa như một bài toán ghép cặp lưỡng phân (bipartite matching) và giải quyết bằng luồng cực đại. Mục tiêu là chọn các đề thi để đáp ứng số lượng yêu cầu cho từng loại đề.

Mô hình đồ thị:

• Tạo một nút nguồn S và một nút đích T.
• Đối với mỗi đề thi i, thêm một cạnh từ S đến i với dung lượng 1 (mỗi đề thi chỉ có thể chọn một lần).
• Đối với mỗi loại đề thi j, thêm một cạnh từ j đến T với dung lượng m_j (số lượng đề thi yêu cầu cho loại j).
• Nếu đề thi i thuộc loại j, thêm một cạnh từ i đến j với dung lượng 1.

Nếu luồng cực đại bằng tổng số đề thi yêu cầu (hoặc tổng số đề thi có sẵn nếu nhỏ hơn), thì có một giải pháp hợp lệ. Để in ra giải pháp, kiểm tra các cạnh từ đề thi đến loại đề thi có luồng bằng 1.

Mã Nguồn C++: Ngân Hàng Đề Thi

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>

const int INF_QUESTION_FLOW = 1e9 + 7;
const int MAX_QUESTION_NODES = 1005 + 5; // Max N questions + Max K categories + S + T

struct QuestionEdge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

QuestionEdge q_edges[MAX_QUESTION_NODES * MAX_QUESTION_NODES * 2]; // Max edges
int q_head[MAX_QUESTION_NODES];
int q_edge_counter = 1;

int num_categories, num_questions;
int category_demand[MAX_QUESTION_NODES]; // Demands for each category

int q_source, q_sink;

int q_node_levels[MAX_QUESTION_NODES];
int q_current_ptr[MAX_QUESTION_NODES];
long long q_max_flow_result;

void add_q_edge(int u, int v, int cap) {
    q_edges[++q_edge_counter] = {v, q_head[u], cap}; q_head[u] = q_edge_counter;
    q_edges[++q_edge_counter] = {u, q_head[v], 0}; q_head[v] = q_edge_counter;
}

bool bfs_q_flow() {
    std::fill(q_node_levels, q_node_levels + q_sink + 1, 0);
    std::queue<int> q;
    q.push(q_source);
    q_node_levels[q_source] = 1;

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

        for (int i = q_head[u]; i; i = q_edges[i].next_edge_idx) {
            int v = q_edges[i].target_node;
            if (q_edges[i].capacity > 0 && q_node_levels[v] == 0) {
                q_node_levels[v] = q_node_levels[u] + 1;
                q.push(v);
                if (v == q_sink) return true;
            }
        }
    }
    return false;
}

int dfs_q_flow(int u, int flow_limit) {
    if (u == q_sink) return flow_limit;

    int current_pushed = 0;
    for (int& i = q_current_ptr[u]; i; i = q_edges[i].next_edge_idx) {
        int v = q_edges[i].target_node;
        if (q_edges[i].capacity > 0 && q_node_levels[v] == q_node_levels[u] + 1) {
            int pushed = dfs_q_flow(v, std::min(flow_limit - current_pushed, q_edges[i].capacity));
            if (pushed == 0) {
                q_node_levels[v] = 0; // Pruning
                continue;
            }
            q_edges[i].capacity -= pushed;
            q_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void dinic_solve_question_bank() {
    while (bfs_q_flow()) {
        std::memcpy(q_current_ptr, q_head, sizeof(int) * (q_sink + 1));
        q_max_flow_result += dfs_q_flow(q_source, INF_QUESTION_FLOW);
    }
}

std::vector<int> assigned_questions[MAX_QUESTION_NODES];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_categories >> num_questions;

    q_source = 0;
    q_sink = num_questions + num_categories + 1;
    int total_demand_sum = 0;

    // Categories are nodes num_questions+1 to num_questions+num_categories
    for (int i = 1; i <= num_categories; ++i) {
        std::cin >> category_demand[i];
        total_demand_sum += category_demand[i];
        add_q_edge(num_questions + i, q_sink, category_demand[i]);
    }

    // Questions are nodes 1 to num_questions
    for (int i = 1; i <= num_questions; ++i) {
        add_q_edge(q_source, i, 1); // Each question can be used once
        int k_categories;
        std::cin >> k_categories;
        while (k_categories--) {
            int category_idx;
            std::cin >> category_idx;
            add_q_edge(i, num_questions + category_idx, 1); // Question i can be used for category category_idx
        }
    }

    dinic_solve_question_bank();

    if (q_max_flow_result != total_demand_sum) {
        std::cout <> "No Solution!" << std::endl;
        return 0;
    }

    std::cout <> "1" << std::endl; // Yes, a solution exists
    for (int p_question = 1; p_question <= num_questions; ++p_question) {
        for (int i = q_head[p_question]; i; i = q_edges[i].next_edge_idx) {
            // If edge is from a question to a category, and its residual capacity is 0,
            // it means flow (matching) occurred
            if (q_edges[i].target_node > num_questions && q_edges[i].target_node <= num_questions + num_categories && q_edges[i].capacity == 0) {
                assigned_questions[q_edges[i].target_node - num_questions].push_back(p_question);
            }
        }
    }

    for (int i = 1; i <= num_categories; ++i) {
        std::cout <> i << ":";
        for (int q_idx : assigned_questions[i]) {
            std::cout <> " " << q_idx;
        }
        std::cout << std::endl;
    }

    return 0;
}

Bài Toán Bao Phủ Đường Đi Tối Thiểu Trên DAG

Bài toán này yêu cầu tìm số lượng đường đi tối thiểu để bao phủ tất cả các nút trong một đồ thị có hướng không chu trình (DAG). Kết quả được tính bằng N - Maximum_Matching, trong đó N là tổng số nút và Maximum_Matching là số cặp đường đi có thể hợp nhất.

Mô hình đồ thị chuyển đổi:

• Đối với mỗi nút u trong DAG gốc, tạo hai nút trong đồ thị lưỡng phân: một nút u_in (nút đầu vào) và một nút u_out (nút đầu ra).
• Tạo một nút nguồn S và một nút đích T.
• Đối với mỗi nút u, thêm một cạnh từ S đến u_in với dung lượng 1.
• Đối với mỗi nút u, thêm một cạnh từ u_out đến T với dung lượng 1.
• Đối với mỗi cạnh (u, v) trong DAG gốc, thêm một cạnh từ u_in đến v_out với dung lượng 1.

Luồng cực đại trong mạng này sẽ là kích thước của ghép cặp cực đại trong đồ thị lưỡng phân, đại diện cho số lượng đường đi có thể được hợp nhất. Số lượng đường đi tối thiểu để bao phủ tất cả các nút là N - max_flow. Để in ra các đường đi, ta truy vết các cạnh đã được sử dụng (luồng bằng 1) từ u_in đến v_out.

Mã Nguồn C++: Bao Phủ Đường Đi Tối Thiểu

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>

const int INF_PATH_COVER_FLOW = 1e9 + 7;
const int MAX_PATH_COVER_NODES = 155; // Max N nodes * 2 (in/out) + S + T

struct PC_Edge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

PC_Edge pc_edges[MAX_PATH_COVER_NODES * MAX_PATH_COVER_NODES * 2]; // Max edges
int pc_head[MAX_PATH_COVER_NODES * 2]; // 2*N nodes for in/out
int pc_edge_counter = 1;

int num_dag_nodes, num_dag_edges;
int pc_source, pc_sink;

int pc_node_levels[MAX_PATH_COVER_NODES * 2];
int pc_current_ptr[MAX_PATH_COVER_NODES * 2];
long long pc_max_flow_result;

void add_pc_edge(int u, int v, int cap) {
    pc_edges[++pc_edge_counter] = {v, pc_head[u], cap}; pc_head[u] = pc_edge_counter;
    pc_edges[++pc_edge_counter] = {u, pc_head[v], 0}; pc_head[v] = pc_edge_counter;
}

bool bfs_pc_flow() {
    std::fill(pc_node_levels, pc_node_levels + pc_sink + 1, 0);
    std::queue<int> q;
    q.push(pc_source);
    pc_node_levels[pc_source] = 1;

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

        for (int i = pc_head[u]; i; i = pc_edges[i].next_edge_idx) {
            int v = pc_edges[i].target_node;
            if (pc_edges[i].capacity > 0 && pc_node_levels[v] == 0) {
                pc_node_levels[v] = pc_node_levels[u] + 1;
                q.push(v);
                if (v == pc_sink) return true;
            }
        }
    }
    return false;
}

int dfs_pc_flow(int u, int flow_limit) {
    if (u == pc_sink) return flow_limit;

    int current_pushed = 0;
    for (int& i = pc_current_ptr[u]; i; i = pc_edges[i].next_edge_idx) {
        int v = pc_edges[i].target_node;
        if (pc_edges[i].capacity > 0 && pc_node_levels[v] == pc_node_levels[u] + 1) {
            int pushed = dfs_pc_flow(v, std::min(flow_limit - current_pushed, pc_edges[i].capacity));
            if (pushed == 0) {
                pc_node_levels[v] = 0; // Pruning
                continue;
            }
            pc_edges[i].capacity -= pushed;
            pc_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void dinic_solve_path_cover() {
    while (bfs_pc_flow()) {
        std::memcpy(pc_current_ptr, pc_head, sizeof(int) * (pc_sink + 1));
        pc_max_flow_result += dfs_pc_flow(pc_source, INF_PATH_COVER_FLOW);
    }
}

int next_node_in_path[MAX_PATH_COVER_NODES]; // Stores u -> v where v is next in path
bool is_path_start[MAX_PATH_COVER_NODES]; // Marks if a node is the start of a path

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_dag_nodes >> num_dag_edges;

    pc_source = 0;
    pc_sink = 2 * num_dag_nodes + 1; // Nodes 1 to N for u_in, N+1 to 2N for u_out

    // Edges from original DAG (u to v) become u_in to v_out
    for (int i = 0; i < num_dag_edges; ++i) {
        int u, v;
        std::cin >> u >> v;
        add_pc_edge(u, v + num_dag_nodes, 1);
    }

    // Connect source to all u_in nodes, and all u_out nodes to sink
    for (int i = 1; i <= num_dag_nodes; ++i) {
        add_pc_edge(pc_source, i, 1);             // S -> u_in
        add_pc_edge(i + num_dag_nodes, pc_sink, 1); // u_out -> T
    }

    dinic_solve_path_cover();

    // Reconstruct paths
    // For each u_in node (1 to num_dag_nodes)
    for (int u_actual = 1; u_actual <= num_dag_nodes; ++u_actual) {
        bool found_match = false;
        for (int i = pc_head[u_actual]; i; i = pc_edges[i].next_edge_idx) {
            int v_out = pc_edges[i].target_node;
            // Check if this edge is from u_in to v_out, and has been used (capacity 0)
            if (v_out > num_dag_nodes && v_out <= 2 * num_dag_nodes && pc_edges[i].capacity == 0) {
                next_node_in_path[u_actual] = v_out - num_dag_nodes; // Store v_actual as next node
                is_path_start[v_out - num_dag_nodes] = true; // Mark v_actual as an intermediate node, not path start
                found_match = true;
                break;
            }
        }
    }

    for (int i = 1; i <= num_dag_nodes; ++i) {
        if (is_path_start[i]) continue; // If node i is not a start of a path, skip (it's covered by a previous path)
        
        int current = i;
        while (current != 0) { // While there's a next node in this path
            std::cout <> current << " ";
            current = next_node_in_path[current];
        }
        std::cout << '\n';
    }

    std::cout <> num_dag_nodes - pc_max_flow_result << '\n';

    return 0;
}

Bài Toán Quả Cầu Ma Thuật

Đây là một biến thể của bài toán bao phủ đường đi tối thiểu trên DAG. Chúng ta cần tìm số lượng số nguyên lớn nhất có thể đặt vào các cột sao cho tổng của hai số liền kề trong bất kỳ cột nào là một số chính phương. Điều này tương đương với việc tìm kích thước lớn nhất của một tập hợp các số sao cho DAG được tạo ra có bao phủ đường đi tối thiểu không vượt quá N (số cột).

Mô hình:

• Thêm các số nguyên vào đồ thị từng bước, bắt đầu từ 1.
• Mỗi số nguyên i được thêm vào tương ứng với hai nút i_in và i_out.
• Một cạnh từ i_in đến j_out (với j < i) được thêm nếu j + i là một số chính phương.
• Đối với mỗi số mới được thêm, chạy thuật toán luồng cực đại để tính bao phủ đường đi tối thiểu. Nếu bao phủ vượt quá N, thì số vừa thêm là quá lớn và số lớn nhất có thể là số trước đó.

Mã Nguồn C++: Quả Cầu Ma Thuật

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;cmath> // For sqrt

const int INF_MAGIC_BALL_FLOW = 1e9 + 7;
const int MAX_BALL_NODES = 7005; // Max node index for M, 2M for in/out, S, T

struct MB_Edge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

MB_Edge mb_edges[MAX_BALL_NODES * 10]; // Max edges (approx M * M)
int mb_head[MAX_BALL_NODES]; // Total nodes = 2*M + S + T
int mb_edge_counter = 1;

int num_columns;
int mb_source, mb_sink;

int mb_node_levels[MAX_BALL_NODES];
int mb_current_ptr[MAX_BALL_NODES];
long long mb_max_flow_result;

void add_mb_edge(int u, int v, int cap) {
    mb_edges[++mb_edge_counter] = {v, mb_head[u], cap}; mb_head[u] = mb_edge_counter;
    mb_edges[++mb_edge_counter] = {u, mb_head[v], 0}; mb_head[v] = mb_edge_counter;
}

bool is_perfect_square(int n) {
    int root = static_cast<int>(std::sqrt(n));
    return root * root == n;
}

bool bfs_mb_flow() {
    std::fill(mb_node_levels, mb_node_levels + mb_sink + 1, 0);
    std::queue<int> q;
    q.push(mb_source);
    mb_node_levels[mb_source] = 1;

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

        for (int i = mb_head[u]; i; i = mb_edges[i].next_edge_idx) {
            int v = mb_edges[i].target_node;
            if (mb_edges[i].capacity > 0 && mb_node_levels[v] == 0) {
                mb_node_levels[v] = mb_node_levels[u] + 1;
                q.push(v);
                if (v == mb_sink) return true;
            }
        }
    }
    return false;
}

int dfs_mb_flow(int u, int flow_limit) {
    if (u == mb_sink) return flow_limit;

    int current_pushed = 0;
    for (int& i = mb_current_ptr[u]; i; i = mb_edges[i].next_edge_idx) {
        int v = mb_edges[i].target_node;
        if (mb_edges[i].capacity > 0 && mb_node_levels[v] == mb_node_levels[u] + 1) {
            int pushed = dfs_mb_flow(v, std::min(flow_limit - current_pushed, mb_edges[i].capacity));
            if (pushed == 0) {
                mb_node_levels[v] = 0; // Pruning
                continue;
            }
            mb_edges[i].capacity -= pushed;
            mb_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void dinic_solve_magic_ball() {
    mb_max_flow_result = 0; // Reset flow for each iteration
    while (bfs_mb_flow()) {
        std::memcpy(mb_current_ptr, mb_head, sizeof(int) * (mb_sink + 1));
        mb_max_flow_result += dfs_mb_flow(mb_source, INF_MAGIC_BALL_FLOW);
    }
}

int next_ball_in_path[MAX_BALL_NODES]; // Stores u -> v where v is next in path
bool is_ball_path_covered[MAX_BALL_NODES]; // Marks if a node is part of a path (not start)

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_columns;

    int max_num_for_paths = 3500; // Heuristic upper bound for numbers
    mb_source = 0;
    mb_sink = max_num_for_paths * 2 + 1; // Nodes 1 to M for in, M+1 to 2M for out

    for (int current_number = 1; ; ++current_number) {
        // Add current_number_in and current_number_out nodes
        // Map current_number to current_number_in, and current_number + max_num_for_paths to current_number_out
        add_mb_edge(mb_source, current_number, 1);
        add_mb_edge(current_number + max_num_for_paths, mb_sink, 1);

        // Connect previous numbers to current_number if sum is perfect square
        for (int prev_number = 1; prev_number < current_number; ++prev_number) {
            if (is_perfect_square(current_number + prev_number)) {
                add_mb_edge(prev_number, current_number + max_num_for_paths, 1);
            }
        }
        
        dinic_solve_magic_ball();

        // Path cover = Total nodes - max_flow. Here, nodes are numbers, so current_number - mb_max_flow_result
        if (current_number - mb_max_flow_result > num_columns) {
            std::cout <> current_number - 1 << '\n'; // Previous number was the max
            
            // Reconstruct paths for current_number - 1
            std::fill(next_ball_in_path, next_ball_in_path + max_num_for_paths, 0);
            std::fill(is_ball_path_covered, is_ball_path_covered + max_num_for_paths, false);

            for (int u_num = 1; u_num < current_number; ++u_num) {
                for (int i = mb_head[u_num]; i; i = mb_edges[i].next_edge_idx) {
                    int v_out = mb_edges[i].target_node;
                    if (v_out > max_num_for_paths && v_out <= 2 * max_num_for_paths && mb_edges[i].capacity == 0) {
                        next_ball_in_path[u_num] = v_out - max_num_for_paths;
                        is_ball_path_covered[v_out - max_num_for_paths] = true;
                        break;
                    }
                }
            }

            for (int i = 1; i < current_number; ++i) {
                if (is_ball_path_covered[i]) continue; // If node i is covered by another path, skip

                int current_ball = i;
                while (current_ball != 0) {
                    std::cout <> current_ball << " ";
                    current_ball = next_ball_in_path[current_ball];
                }
                std::cout << '\n';
            }
            return 0;
        }
    }

    return 0;
}

Bài Toán Dãy Con Không Giảm Dài Nhất

Bài toán này mở rộng vấn đề dãy con không giảm dài nhất (LIS) kinh điển bằng cách hỏi về số lượng dãy con như vậy và khả năng thay đổi một số giới hạn.

Phần 1: Chiều dài của dãy con không giảm dài nhất (LIS) là một bài toán quy hoạch động tiêu chuẩn. dp[i] là độ dài LIS kết thúc tại a[i].

Phần 2: Số lượng dãy con không giảm dài nhất có thể được tìm bằng luồng mạng.

• Mỗi số a[i] được chia thành hai nút: i_in và i_out. Một cạnh từ i_in đến i_out với dung lượng 1 (mỗi số chỉ được sử dụng một lần).
• Nếu a[j] ≤ a[i] và dp[j] + 1 == dp[i], thêm một cạnh từ j_out đến i_in với dung lượng 1.
• Nếu dp[i] == 1, thêm cạnh từ nguồn S đến i_in với dung lượng 1.
• Nếu dp[i] == LIS_length, thêm cạnh từ i_out đến đích T với dung lượng 1.

Luồng cực đại trong mạng này sẽ là số lượng dãy con không giảm dài nhất có thể được chọn mà không có phần tử nào trùng nhau.

Phần 3: Thay đổi giới hạn cho phần tử đầu tiên và cuối cùng.

• Thay đổi dung lượng từ S đến 1_in thành vô hạn.
• Thay đổi dung lượng từ 1_in đến 1_out thành vô hạn.
• Thay đổi dung lượng từ n_in đến n_out thành vô hạn.
• Nếu dp[n] == LIS_length, thay đổi dung lượng từ n_out đến T thành vô hạn.

Sau khi thay đổi dung lượng, chạy lại thuật toán luồng cực đại. Cần xử lý trường hợp đặc biệt n=1.

Mã Nguồn C++: Dãy Con Không Giảm Dài Nhất

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>

const int INF_LIS_FLOW = 1e9 + 7;
const int MAX_LIS_NODES = 1005; // Max N * 2 (in/out) + S + T

struct LIS_Edge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

LIS_Edge lis_edges[MAX_LIS_NODES * MAX_LIS_NODES * 2]; // Max edges
int lis_head[MAX_LIS_NODES * 2]; // Max N in/out nodes + S + T
int lis_edge_counter = 1;

int num_sequence_elements;
int sequence_values[MAX_LIS_NODES];
int lis_lengths[MAX_LIS_NODES]; // dp[i] for LIS ending at i

int lis_source, lis_sink;

int lis_node_levels[MAX_LIS_NODES * 2];
int lis_current_ptr[MAX_LIS_NODES * 2];
long long lis_max_flow_result;

void add_lis_edge(int u, int v, int cap) {
    lis_edges[++lis_edge_counter] = {v, lis_head[u], cap}; lis_head[u] = lis_edge_counter;
    lis_edges[++lis_edge_counter] = {u, lis_head[v], 0}; lis_head[v] = lis_edge_counter;
}

bool bfs_lis_flow() {
    std::fill(lis_node_levels, lis_node_levels + lis_sink + 1, 0);
    std::queue<int> q;
    q.push(lis_source);
    lis_node_levels[lis_source] = 1;

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

        for (int i = lis_head[u]; i; i = lis_edges[i].next_edge_idx) {
            int v = lis_edges[i].target_node;
            if (lis_edges[i].capacity > 0 && lis_node_levels[v] == 0) {
                lis_node_levels[v] = lis_node_levels[u] + 1;
                q.push(v);
                if (v == lis_sink) return true;
            }
        }
    }
    return false;
}

int dfs_lis_flow(int u, int flow_limit) {
    if (u == lis_sink) return flow_limit;

    int current_pushed = 0;
    for (int& i = lis_current_ptr[u]; i; i = lis_edges[i].next_edge_idx) {
        int v = lis_edges[i].target_node;
        if (lis_edges[i].capacity > 0 && lis_node_levels[v] == lis_node_levels[u] + 1) {
            int pushed = dfs_lis_flow(v, std::min(flow_limit - current_pushed, lis_edges[i].capacity));
            if (pushed == 0) {
                lis_node_levels[v] = 0; // Pruning
                continue;
            }
            lis_edges[i].capacity -= pushed;
            lis_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void dinic_solve_lis() {
    lis_max_flow_result = 0;
    while (bfs_lis_flow()) {
        std::memcpy(lis_current_ptr, lis_head, sizeof(int) * (lis_sink + 1));
        lis_max_flow_result += dfs_lis_flow(lis_source, INF_LIS_FLOW);
    }
}

// Function to update capacity of a specific edge
void update_edge_capacity(int u, int v, int new_cap) {
    for (int i = lis_head[u]; i; i = lis_edges[i].next_edge_idx) {
        if (lis_edges[i].target_node == v) {
            lis_edges[i].capacity = new_cap;
            return;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_sequence_elements;

    if (num_sequence_elements == 1) {
        std::cout <> 1 << std::endl;
        std::cout <> 1 << std::endl;
        std::cout <> 1 << std::endl;
        return 0;
    }

    for (int i = 1; i <= num_sequence_elements; ++i) std::cin >> sequence_values[i];

    // Part 1: Calculate LIS lengths
    for (int i = 1; i <= num_sequence_elements; ++i) {
        lis_lengths[i] = 1; // Minimum LIS length is 1 (the element itself)
        for (int j = 1; j < i; ++j) {
            if (sequence_values[j] <= sequence_values[i]) {
                lis_lengths[i] = std::max(lis_lengths[i], lis_lengths[j] + 1);
            }
        }
    }

    int overall_lis_length = 0;
    for (int i = 1; i <= num_sequence_elements; ++i) {
        overall_lis_length = std::max(overall_lis_length, lis_lengths[i]);
    }
    std::cout <> overall_lis_length << std::endl;

    // Part 2: Max number of LIS that are disjoint
    lis_source = 0;
    lis_sink = 2 * num_sequence_elements + 1; // Nodes 1 to N (in), N+1 to 2N (out)

    for (int i = 1; i <= num_sequence_elements; ++i) {
        add_lis_edge(i, i + num_sequence_elements, 1); // Capacity 1 for each element

        if (lis_lengths[i] == 1) add_lis_edge(lis_source, i, 1); // From source to LIS start
        if (lis_lengths[i] == overall_lis_length) add_lis_edge(i + num_sequence_elements, lis_sink, 1); // From LIS end to sink

        for (int j = 1; j < i; ++j) {
            if (sequence_values[j] <= sequence_values[i] && lis_lengths[j] + 1 == lis_lengths[i]) {
                add_lis_edge(j + num_sequence_elements, i, 1); // Connect LIS transitions
            }
        }
    }
    dinic_solve_lis();
    std::cout <> lis_max_flow_result << std::endl;

    // Part 3: Modified problem with infinite capacity for elements 1 and N
    // Reset network and rebuild relevant parts to modify capacities
    std::memset(lis_head, 0, sizeof(lis_head));
    lis_edge_counter = 1;

    for (int i = 1; i <= num_sequence_elements; ++i) {
        int capacity_mid_edge = (i == 1 || i == num_sequence_elements) ? INF_LIS_FLOW : 1;
        add_lis_edge(i, i + num_sequence_elements, capacity_mid_edge);

        int capacity_from_source = (lis_lengths[i] == 1 && i == 1) ? INF_LIS_FLOW : 1;
        if (lis_lengths[i] == 1) add_lis_edge(lis_source, i, capacity_from_source);
        
        int capacity_to_sink = (lis_lengths[i] == overall_lis_length && i == num_sequence_elements) ? INF_LIS_FLOW : 1;
        if (lis_lengths[i] == overall_lis_length) add_lis_edge(i + num_sequence_elements, lis_sink, capacity_to_sink);

        for (int j = 1; j < i; ++j) {
            if (sequence_values[j] <= sequence_values[i] && lis_lengths[j] + 1 == lis_lengths[i]) {
                add_lis_edge(j + num_sequence_elements, i, 1);
            }
        }
    }
    dinic_solve_lis();
    std::cout <> lis_max_flow_result << std::endl;

    return 0;
}

Bài Toán Lộ Trình Hàng Không

Bài toán này yêu cầu tìm hai đường đi từ điểm khởi hành 1 đến điểm đích N mà không giao nhau (ngoại trừ tại điểm 1 và N) sao cho tổng chiều dài của chúng là lớn nhất. Đây là một bài toán đường đi có trọng số hạn chế (Restricted Weighted Path), có thể được giải quyết bằng thuật toán Min-Cost Max-Flow.

Mô hình đồ thị:

• Mỗi thành phố i được chia thành hai nút: i_in và i_out.
• Đối với mỗi thành phố i, thêm một cạnh từ i_in đến i_out với dung lượng 1, chi phí 0 (đảm bảo mỗi thành phố chỉ được đi qua một lần, trừ 1 và N).
• Đối với mỗi đường bay (u, v), thêm một cạnh từ u_out đến v_in với dung lượng 1, chi phí -1 (để tối đa hóa chiều dài, ta tối thiểu hóa chi phí âm).
• Từ nguồn S đến 1_in với dung lượng 2, chi phí 0 (hai đường đi bắt đầu từ 1).
• Từ N_out đến đích T với dung lượng 2, chi phí 0 (hai đường đi kết thúc tại N).

Nếu luồng cực đại là 2, thì chi phí nhỏ nhất tìm được là âm của tổng chiều dài đường đi. Cần xử lý trường hợp đặc biệt khi chỉ có một đường đi hoặc đường đi quay vòng.

Mã Nguồn C++: Lộ Trình Hàng Không

#include <iostream>
#include <vector>
#lt;string>
#lt;map>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const int INF_ROUTE_COST = 1e9 + 7;
const long long INF_ROUTE_LL = std::numeric_limits<long long>::max() / 2;
const int MAX_ROUTE_NODES = 305; // Max N * 2 (in/out) + S + T

struct RouteEdge {
    int target_node;
    int next_edge_idx;
    int flow_capacity;
    int edge_cost;
};

RouteEdge route_edges[MAX_ROUTE_NODES * MAX_ROUTE_NODES * 2]; // Max edges
int route_head[MAX_ROUTE_NODES * 2]; // Max N in/out nodes + S + T
int route_edge_counter = 1;

int num_cities, num_flights;
std::map<std::string, int> city_to_id_map;
std::string id_to_city_names[MAX_ROUTE_NODES];
int current_city_id_counter = 0;

int route_source, route_sink;

long long route_min_cost_dist[MAX_ROUTE_NODES * 2];
int route_path_parent_nodes[MAX_ROUTE_NODES * 2];
int route_path_edge_indices[MAX_ROUTE_NODES * 2];
bool route_in_queue[MAX_ROUTE_NODES * 2];

long long total_route_flow = 0;
long long total_route_min_cost = 0;

void add_route_edge(int u, int v, int capacity, int cost) {
    route_edges[++route_edge_counter] = {v, route_head[u], capacity, cost}; route_head[u] = route_edge_counter;
    route_edges[++route_edge_counter] = {u, route_head[v], 0, -cost}; route_head[v] = route_edge_counter;
}

bool spfa_route_shortest_path() {
    std::fill(route_min_cost_dist, route_min_cost_dist + route_sink + 1, INF_ROUTE_LL);
    std::fill(route_in_queue, route_in_queue + route_sink + 1, false);
    std::queue<int> q_spfa;

    route_min_cost_dist[route_source] = 0;
    q_spfa.push(route_source);
    route_in_queue[route_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        route_in_queue[u] = false;

        for (int i = route_head[u]; i; i = route_edges[i].next_edge_idx) {
            RouteEdge& edge = route_edges[i];
            if (edge.flow_capacity > 0 && route_min_cost_dist[edge.target_node] > route_min_cost_dist[u] + edge.edge_cost) {
                route_min_cost_dist[edge.target_node] = route_min_cost_dist[u] + edge.edge_cost;
                route_path_parent_nodes[edge.target_node] = u;
                route_path_edge_indices[edge.target_node] = i;

                if (!route_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    route_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return route_min_cost_dist[route_sink] != INF_ROUTE_LL;
}

void find_min_cost_max_flow_route() {
    total_route_flow = 0;
    total_route_min_cost = 0;
    while (spfa_route_shortest_path()) {
        long long current_path_flow = INF_ROUTE_LL;

        for (int v = route_sink; v != route_source; v = route_path_parent_nodes[v]) {
            int u = route_path_parent_nodes[v];
            int edge_idx = route_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, (long long)route_edges[edge_idx].flow_capacity);
        }

        total_route_flow += current_path_flow;
        total_route_min_cost += current_path_flow * route_min_cost_dist[route_sink];

        for (int v = route_sink; v != route_source; v = route_path_parent_nodes[v]) {
            int u = route_path_parent_nodes[v];
            int edge_idx = route_path_edge_indices[v];
            route_edges[edge_idx].flow_capacity -= current_path_flow;
            route_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

bool visited_for_path_output[MAX_ROUTE_NODES * 2];

void print_path1(int u_city) {
    std::cout <> id_to_city_names[u_city] << std::endl;
    visited_for_path_output[u_city] = true;

    // Iterate through outgoing edges from u_out node
    for (int i = route_head[u_city + num_cities]; i; i = route_edges[i].next_edge_idx) {
        int v_city = route_edges[i].target_node;
        // If it's an edge to v_in, and it's full (capacity 0) and not visited, follow it
        if (v_city >= 1 && v_city <= num_cities && route_edges[i].flow_capacity == 0 && !visited_for_path_output[v_city]) {
            print_path1(v_city);
            return; // Found and followed one path
        }
    }
}

void print_path2(int u_city) {
    // Traverse in reverse order (DFS)
    for (int i = route_head[u_city + num_cities]; i; i = route_edges[i].next_edge_idx) {
        int v_city = route_edges[i].target_node;
        if (v_city >= 1 && v_city <= num_cities && route_edges[i].flow_capacity == 0 && !visited_for_path_output[v_city]) {
            print_path2(v_city);
        }
    }
    std::cout <> id_to_city_names[u_city] << std::endl;
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_cities >> num_flights;

    for (int i = 1; i <= num_cities; ++i) {
        std::string city_name;
        std::cin >> city_name;
        city_to_id_map[city_name] = i;
        id_to_city_names[i] = city_name;
    }

    // Cities are 1 to num_cities.
    // u_in is u, u_out is u + num_cities
    route_source = 0;
    route_sink = 2 * num_cities + 1;

    // Internal edges for cities (u_in -> u_out)
    for (int i = 1; i <= num_cities; ++i) {
        int capacity_val = (i == 1 || i == num_cities) ? 2 : 1; // Start/End nodes can be visited twice (by two paths)
        add_route_edge(i, i + num_cities, capacity_val, 0); // Cost 0 for passing through
    }

    // Flight connections (u_out -> v_in)
    for (int i = 0; i < num_flights; ++i) {
        std::string city_a_name, city_b_name;
        std::cin >> city_a_name >> city_b_name;
        int u_id = city_to_id_map[city_a_name];
        int v_id = city_to_id_map[city_b_name];
        
        // Problem implies direction, but routes can be taken either way
        // "from A to B or from B to A" is not explicitly stated.
        // The original code implies u > v swap, suggesting bidirectional or sorted pairs for processing.
        // Let's assume directed flights as given.
        add_route_edge(u_id + num_cities, v_id, 1, -1); // Cost -1 to maximize path length
    }

    // Source to start city (1_in), start city (1_out) to sink.
    add_route_edge(route_source, 1, 2, 0); // Two paths from source to city 1
    add_route_edge(num_cities + num_cities, route_sink, 2, 0); // Two paths from city N to sink

    find_min_cost_max_flow_route();

    if (total_route_flow != 2) {
        // Handle case where two disjoint paths aren't found
        // If max flow is 1, and min cost is -1 (meaning 1 -> N path exists), and N-1 is 1-N.
        // The problem is asking for two _disjoint_ paths.
        // If total flow is 1 and min cost is -1, it implies 1 -> N path is found.
        // Original code handles a special case: path 1 -> N -> 1.
        if (total_route_flow == 1 && total_route_min_cost == -1 && num_cities == 2) { // 1->N->1 for two cities
            std::cout <> 2 << std::endl;
            std::cout <> id_to_city_names[1] << std::endl;
            std::cout <> id_to_city_names[num_cities] << std::endl;
            std::cout <> id_to_city_names[1] << std::endl;
            return 0;
        }
        std::cout <> "No Solution!" << std::endl;
        return 0;
    }
    
    std::cout <> -total_route_min_cost << std::endl; // Output positive total length

    std::fill(visited_for_path_output, visited_for_path_output + num_cities + 1, false);
    print_path1(1); // Print first path
    print_path2(1); // Print second path (by finding unvisited branches)

    return 0;
}

Bài Toán Lấy Số Từ Ô Vuông

Bài toán này yêu cầu chọn các số từ một lưới ô vuông sao cho không có hai số nào được chọn nằm cạnh nhau (trên, dưới, trái, phải), và tổng các số được chọn là lớn nhất. Đây là một bài toán tìm tập hợp độc lập có trọng số cực đại trên đồ thị lưỡng phân (Maximum Weighted Independent Set on a Bipartite Graph), có thể giải bằng cách chuyển đổi sang bài toán Min-Cut (cắt cực tiểu).

Mô hình đồ thị:

• Tô màu bàn cờ đen trắng cho lưới ô vuông. Các ô đen và các ô trắng tạo thành hai tập hợp của một đồ thị lưỡng phân. Các cạnh tồn tại giữa các ô liền kề có màu khác nhau.
• Tổng trọng số của tập hợp độc lập cực đại bằng tổng trọng số của tất cả các nút trừ đi trọng số của bao phủ nút cực tiểu (Minimum Vertex Cover).
• Chuyển đổi sang Min-Cut:
  • Tạo một nút nguồn S và một nút đích T.
  • Đối với mỗi ô đen (i, j), thêm một cạnh từ S đến nút tương ứng của nó với dung lượng là giá trị số của ô a[i][j].
  • Đối với mỗi ô trắng (i, j), thêm một cạnh từ nút tương ứng của nó đến T với dung lượng là giá trị số của ô a[i][j].
  • Đối với mỗi cặp ô liền kề (một đen, một trắng), thêm một cạnh từ ô đen đến ô trắng với dung lượng vô hạn.

Min-Cut của đồ thị này sẽ tương đương với giá trị của bao phủ nút cực tiểu. Tổng trọng số cực đại là Tổng_Tất_Cả_Số - Min_Cut.

Mã Nguồn C++: Lấy Số Từ Ô Vuông

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>

const int INF_GRID_FLOW = 1e9 + 7;
const int MAX_GRID_DIM = 105; // Max N, M dimensions
const int MAX_GRID_NODES = MAX_GRID_DIM * MAX_GRID_DIM + 5; // N*M nodes + S + T

struct GridEdge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

GridEdge grid_edges[MAX_GRID_NODES * 8]; // Max edges (N*M nodes, each up to 4 neighbors)
int grid_head[MAX_GRID_NODES];
int grid_edge_counter = 1;

int grid_rows, grid_cols;
int grid_values[MAX_GRID_DIM][MAX_GRID_DIM];

int grid_source, grid_sink;

int grid_node_levels[MAX_GRID_NODES];
int grid_current_ptr[MAX_GRID_NODES];
long long grid_max_flow_result;

// Helper to get a unique node ID for grid cell (r, c)
inline int get_grid_node_id(int r, int c) {
    return (r - 1) * grid_cols + c;
}

void add_grid_edge(int u, int v, int cap) {
    grid_edges[++grid_edge_counter] = {v, grid_head[u], cap}; grid_head[u] = grid_edge_counter;
    grid_edges[++grid_edge_counter] = {u, grid_head[v], 0}; grid_head[v] = grid_edge_counter;
}

bool bfs_grid_flow() {
    std::fill(grid_node_levels, grid_node_levels + grid_sink + 1, 0);
    std::queue<int> q;
    q.push(grid_source);
    grid_node_levels[grid_source] = 1;

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

        for (int i = grid_head[u]; i; i = grid_edges[i].next_edge_idx) {
            int v = grid_edges[i].target_node;
            if (grid_edges[i].capacity > 0 && grid_node_levels[v] == 0) {
                grid_node_levels[v] = grid_node_levels[u] + 1;
                q.push(v);
                if (v == grid_sink) return true;
            }
        }
    }
    return false;
}

int dfs_grid_flow(int u, int flow_limit) {
    if (u == grid_sink) return flow_limit;

    int current_pushed = 0;
    for (int& i = grid_current_ptr[u]; i; i = grid_edges[i].next_edge_idx) {
        int v = grid_edges[i].target_node;
        if (grid_edges[i].capacity > 0 && grid_node_levels[v] == grid_node_levels[u] + 1) {
            int pushed = dfs_grid_flow(v, std::min(flow_limit - current_pushed, grid_edges[i].capacity));
            if (pushed == 0) {
                grid_node_levels[v] = 0; // Pruning
                continue;
            }
            grid_edges[i].capacity -= pushed;
            grid_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void dinic_solve_grid_problem() {
    while (bfs_grid_flow()) {
        std::memcpy(grid_current_ptr, grid_head, sizeof(int) * (grid_sink + 1));
        grid_max_flow_result += dfs_grid_flow(grid_source, INF_GRID_FLOW);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> grid_rows >> grid_cols;

    long long total_sum_all_values = 0;
    for (int i = 1; i <= grid_rows; ++i) {
        for (int j = 1; j <= grid_cols; ++j) {
            std::cin >> grid_values[i][j];
            total_sum_all_values += grid_values[i][j];
        }
    }

    grid_source = 0;
    grid_sink = grid_rows * grid_cols + 1;

    // Directions for neighbors (up, down, left, right)
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    for (int r = 1; r <= grid_rows; ++r) {
        for (int c = 1; c <= grid_cols; ++c) {
            int current_node_id = get_grid_node_id(r, c);
            if ((r + c) % 2 == 1) { // Black cell (or one color set in bipartite graph)
                add_grid_edge(grid_source, current_node_id, grid_values[r][c]);
                // Connect to neighbors (which will be white cells)
                for (int k = 0; k < 4; ++k) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (nr >= 1 && nr <= grid_rows && nc >= 1 && nc <= grid_cols) {
                        add_grid_edge(current_node_id, get_grid_node_id(nr, nc), INF_GRID_FLOW);
                    }
                }
            } else { // White cell (the other color set)
                add_grid_edge(current_node_id, grid_sink, grid_values[r][c]);
            }
        }
    }

    dinic_solve_grid_problem();

    // Max Weighted Independent Set = Total Sum - Min Cut (Min Vertex Cover)
    std::cout <> total_sum_all_values - grid_max_flow_result << std::endl;

    return 0;
}

Bài Toán Bố Trí Bàn Tròn

Bài toán này yêu cầu bố trí các đại biểu từ các đơn vị khác nhau vào các bàn tròn sao cho mỗi đơn vị có số lượng đại biểu nhất định và mỗi bàn có sức chứa nhất định. Đây là một bài toán ghép cặp lưỡng phân (bipartite matching) có thể giải bằng luồng cực đại.

Mô hình đồ thị:

• Tạo một nút nguồn S và một nút đích T.
• Đối với mỗi đơn vị i, thêm một cạnh từ S đến i với dung lượng r_i (số đại biểu của đơn vị i).
• Đối với mỗi bàn j, thêm một cạnh từ j đến T với dung lượng c_j (sức chứa của bàn j).
• Đối với mỗi đơn vị i và mỗi bàn j, thêm một cạnh từ i đến j với dung lượng 1 (mỗi đại biểu từ đơn vị i có thể ngồi vào bàn j).

Nếu luồng cực đại bằng tổng số đại biểu, thì có một giải pháp hợp lệ. Để in ra giải pháp, kiểm tra các cạnh từ đơn vị đến bàn có luồng bằng 1.

Mã Nguồn C++: Bố Trí Bàn Tròn

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>

const int INF_TABLE_FLOW = 1e9 + 7;
const int MAX_TABLE_NODES = 505; // Max N units + M tables + S + T

struct TableEdge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

TableEdge table_edges[MAX_TABLE_NODES * MAX_TABLE_NODES * 2]; // Max N*M edges
int table_head[MAX_TABLE_NODES * 2]; // N units, M tables
int table_edge_counter = 1;

int num_units, num_tables;
int unit_delegates_count[MAX_TABLE_NODES];
int table_capacity[MAX_TABLE_NODES];

int table_source, table_sink;

int table_node_levels[MAX_TABLE_NODES * 2];
int table_current_ptr[MAX_TABLE_NODES * 2];
long long table_max_flow_result;

void add_table_edge(int u, int v, int cap) {
    table_edges[++table_edge_counter] = {v, table_head[u], cap}; table_head[u] = table_edge_counter;
    table_edges[++table_edge_counter] = {u, table_head[v], 0}; table_head[v] = table_edge_counter;
}

bool bfs_table_flow() {
    std::fill(table_node_levels, table_node_levels + table_sink + 1, 0);
    std::queue<int> q;
    q.push(table_source);
    table_node_levels[table_source] = 1;

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

        for (int i = table_head[u]; i; i = table_edges[i].next_edge_idx) {
            int v = table_edges[i].target_node;
            if (table_edges[i].capacity > 0 && table_node_levels[v] == 0) {
                table_node_levels[v] = table_node_levels[u] + 1;
                q.push(v);
                if (v == table_sink) return true;
            }
        }
    }
    return false;
}

int dfs_table_flow(int u, int flow_limit) {
    if (u == table_sink) return flow_limit;

    int current_pushed = 0;
    for (int& i = table_current_ptr[u]; i; i = table_edges[i].next_edge_idx) {
        int v = table_edges[i].target_node;
        if (table_edges[i].capacity > 0 && table_node_levels[v] == table_node_levels[u] + 1) {
            int pushed = dfs_table_flow(v, std::min(flow_limit - current_pushed, table_edges[i].capacity));
            if (pushed == 0) {
                table_node_levels[v] = 0; // Pruning
                continue;
            }
            table_edges[i].capacity -= pushed;
            table_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void dinic_solve_round_table() {
    while (bfs_table_flow()) {
        std::memcpy(table_current_ptr, table_head, sizeof(int) * (table_sink + 1));
        table_max_flow_result += dfs_table_flow(table_source, INF_TABLE_FLOW);
    }
}

std::vector<int> unit_seat_assignments[MAX_TABLE_NODES];

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_units >> num_tables;

    int total_delegates_needed = 0;
    for (int i = 1; i <= num_units; ++i) {
        std::cin >> unit_delegates_count[i];
        total_delegates_needed += unit_delegates_count[i];
    }
    for (int i = 1; i <= num_tables; ++i) {
        std::cin >> table_capacity[i];
    }

    table_source = 0;
    table_sink = num_units + num_tables + 1; // Units 1 to N, Tables N+1 to N+M

    // Edges from source to units
    for (int i = 1; i <= num_units; ++i) add_table_edge(table_source, i, unit_delegates_count[i]);
    // Edges from tables to sink
    for (int i = 1; i <= num_tables; ++i) add_table_edge(num_units + i, table_sink, table_capacity[i]);
    // Edges from units to tables (each delegate can go to any table)
    for (int i = 1; i <= num_units; ++i) {
        for (int j = 1; j <= num_tables; ++j) {
            add_table_edge(i, num_units + j, 1); // Each delegate has 1 capacity
        }
    }

    dinic_solve_round_table();

    if (table_max_flow_result != total_delegates_needed) {
        std::cout <> 0 << std::endl; // No solution
    } else {
        std::cout <> 1 << std::endl; // Solution exists
        // Output assignments
        for (int u_unit = 1; u_unit <= num_units; ++u_unit) {
            for (int i = table_head[u_unit]; i; i = table_edges[i].next_edge_idx) {
                int v_table_node = table_edges[i].target_node;
                // If this edge is to a table node, and its capacity is 0, it means a delegate was assigned
                if (v_table_node > num_units && v_table_node <= num_units + num_tables && table_edges[i].capacity == 0) {
                    unit_seat_assignments[u_unit].push_back(v_table_node - num_units);
                }
            }
        }
        for (int i = 1; i <= num_units; ++i) {
            for (int assigned_table_idx : unit_seat_assignments[i]) {
                std::cout <> assigned_table_idx << " ";
            }
            std::cout << std::endl;
        }
    }

    return 0;
}

Bài Toán Sĩ Quan Cùng Tồn Tại

Bài toán này yêu cầu đặt số lượng sĩ quan (Knight) tối đa lên một bàn cờ N x N sao cho không có hai sĩ quan nào có thể tấn công lẫn nhau. Một số ô trên bàn cờ có thể bị cấm. Đây là một bài toán tìm tập hợp độc lập cực đại trên đồ thị lưỡng phân, tương tự như bài toán Lấy Số Từ Ô Vuông.

Mô hình đồ thị:

• Tô màu bàn cờ đen trắng. Các ô đen và các ô trắng tạo thành hai tập hợp của một đồ thị lưỡng phân. Các cạnh tồn tại giữa các ô mà một sĩ quan có thể tấn công từ ô này sang ô kia.
• Tổng số ô không bị cấm trừ đi kích thước bao phủ nút cực tiểu sẽ cho ra tập hợp độc lập cực đại.
• Chuyển đổi sang Min-Cut:
  • Tạo một nút nguồn S và một nút đích T.
  • Đối với mỗi ô đen (i, j) không bị cấm, thêm một cạnh từ S đến nút tương ứng của nó với dung lượng 1.
  • Đối với mỗi ô trắng (i, j) không bị cấm, thêm một cạnh từ nút tương ứng của nó đến T với dung lượng 1.
  • Đối với mỗi cặp ô (u, v) mà sĩ quan có thể tấn công (một đen, một trắng), thêm một cạnh từ ô đen u đến ô trắng v với dung lượng vô hạn.

Min-Cut của đồ thị này sẽ tương đương với giá trị của bao phủ nút cực tiểu. Số lượng sĩ quan tối đa là Tổng_Số_Ô_Không_Bị_Cấm - Min_Cut.

Mã Nguồn C++: Sĩ Quan Cùng Tồn Tại

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>

const int INF_KNIGHT_FLOW = 1e9 + 7;
const int MAX_BOARD_DIM = 205; // Max N dimension
const int MAX_BOARD_NODES = MAX_BOARD_DIM * MAX_BOARD_DIM + 5; // N*N nodes + S + T

struct KnightEdge {
    int target_node;
    int next_edge_idx;
    int capacity;
};

KnightEdge knight_edges[MAX_BOARD_NODES * 10]; // Max edges
int knight_head[MAX_BOARD_NODES];
int knight_edge_counter = 1;

int board_size, num_forbidden_cells;
bool forbidden_cells[MAX_BOARD_DIM][MAX_BOARD_DIM]; // True if cell (r, c) is forbidden
int cell_node_ids[MAX_BOARD_DIM][MAX_BOARD_DIM]; // Unique node ID for each cell
int total_valid_cells = 0;

int knight_source, knight_sink;

int knight_node_levels[MAX_BOARD_NODES];
int knight_current_ptr[MAX_BOARD_NODES];
long long knight_max_flow_result;

// Knight moves relative to (r, c)
int dr[] = {-1, -1, 1, 1, -2, -2, 2, 2};
int dc[] = {-2, 2, -2, 2, -1, 1, -1, 1};

void add_knight_edge(int u, int v, int cap) {
    knight_edges[++knight_edge_counter] = {v, knight_head[u], cap}; knight_head[u] = knight_edge_counter;
    knight_edges[++knight_edge_counter] = {u, knight_head[v], 0}; knight_head[v] = knight_edge_counter;
}

bool bfs_knight_flow() {
    std::fill(knight_node_levels, knight_node_levels + knight_sink + 1, 0);
    std::queue<int> q;
    q.push(knight_source);
    knight_node_levels[knight_source] = 1;

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

        for (int i = knight_head[u]; i; i = knight_edges[i].next_edge_idx) {
            int v = knight_edges[i].target_node;
            if (knight_edges[i].capacity > 0 && knight_node_levels[v] == 0) {
                knight_node_levels[v] = knight_node_levels[u] + 1;
                q.push(v);
                if (v == knight_sink) return true;
            }
        }
    }
    return false;
}

int dfs_knight_flow(int u, int flow_limit) {
    if (u == knight_sink) return flow_limit;

    int current_pushed = 0;
    for (int& i = knight_current_ptr[u]; i; i = knight_edges[i].next_edge_idx) {
        int v = knight_edges[i].target_node;
        if (knight_edges[i].capacity > 0 && knight_node_levels[v] == knight_node_levels[u] + 1) {
            int pushed = dfs_knight_flow(v, std::min(flow_limit - current_pushed, knight_edges[i].capacity));
            if (pushed == 0) {
                knight_node_levels[v] = 0; // Pruning
                continue;
            }
            knight_edges[i].capacity -= pushed;
            knight_edges[i ^ 1].capacity += pushed;
            current_pushed += pushed;
            if (current_pushed == flow_limit) break;
        }
    }
    return current_pushed;
}

void dinic_solve_knight_problem() {
    while (bfs_knight_flow()) {
        std::memcpy(knight_current_ptr, knight_head, sizeof(int) * (knight_sink + 1));
        knight_max_flow_result += dfs_knight_flow(knight_source, INF_KNIGHT_FLOW);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> board_size >> num_forbidden_cells;

    for (int i = 0; i < num_forbidden_cells; ++i) {
        int r, c;
        std::cin >> r >> c;
        forbidden_cells[r][c] = true;
    }

    // Assign unique IDs to valid cells and count total_valid_cells
    for (int r = 1; r <= board_size; ++r) {
        for (int c = 1; c <= board_size; ++c) {
            if (!forbidden_cells[r][c]) {
                cell_node_ids[r][c] = ++total_valid_cells;
            }
        }
    }

    knight_source = 0;
    knight_sink = total_valid_cells + 1;

    for (int r = 1; r <= board_size; ++r) {
        for (int c = 1; c <= board_size; ++c) {
            if (forbidden_cells[r][c]) continue; // Skip forbidden cells

            int current_cell_id = cell_node_ids[r][c];
            if ((r + c) % 2 == 1) { // Black cell (one partition of bipartite graph)
                add_knight_edge(knight_source, current_cell_id, 1); // Cost 1 for selecting this cell
                // Connect to all reachable white cells
                for (int k = 0; k < 8; ++k) {
                    int nr = r + dr[k];
                    int nc = c + dc[k];
                    if (nr >= 1 && nr <= board_size && nc >= 1 && nc <= board_size && !forbidden_cells[nr][nc]) {
                        add_knight_edge(current_cell_id, cell_node_ids[nr][nc], INF_KNIGHT_FLOW); // Infinite capacity
                    }
                }
            } else { // White cell (other partition)
                add_knight_edge(current_cell_id, knight_sink, 1); // Cost 1 for selecting this cell
            }
        }
    }

    dinic_solve_knight_problem();

    // Max Independent Set = Total Valid Cells - Min Cut (Min Vertex Cover)
    std::cout <> total_valid_cells - knight_max_flow_result << std::endl;

    return 0;
}

Bài Toán Thám Hiểm Sao Hỏa

Bài toán này yêu cầu tìm K đường đi từ một điểm khởi đầu đến một điểm đích trên một lưới ô vuông, thu thập số lượng mẫu đá tối đa. Mỗi ô có thể chứa một mẫu đá và mỗi đường đi chỉ có thể đi qua một ô một lần để thu thập mẫu đá. Đây là một bài toán đường đi có trọng số hạn chế (Restricted Weighted Path), có thể được giải quyết bằng thuật toán Min-Cost Max-Flow.

Mô hình đồ thị:

• Mỗi ô (i, j) được chia thành hai nút: (i, j)_in và (i, j)_out.
• Đối với mỗi ô (i, j):
  • Thêm một cạnh từ (i, j)_in đến (i, j)_out với dung lượng vô hạn và chi phí 0.
  • Nếu ô (i, j) chứa một mẫu đá, thêm một cạnh từ (i, j)_in đến (i, j)_out với dung lượng 1 và chi phí -1 (để thu thập mẫu đá một lần).
• Đối với các đường di chuyển: Nếu có thể di chuyển từ (i, j) đến (i', j') (xuống hoặc phải), thêm một cạnh từ (i, j)_out đến (i', j')_in với dung lượng vô hạn và chi phí 0.
• Từ nguồn S đến (1, 1)_in với dung lượng K, chi phí 0.
• Từ (N, M)_out đến đích T với dung lượng K, chi phí 0.

Min-Cost Max-Flow sẽ tìm K đường đi với tổng chi phí âm nhỏ nhất, tức là tổng số mẫu đá lớn nhất. Để in ra đường đi, ta truy vết các cạnh đã sử dụng trong đồ thị đối ngẫu.

Mã Nguồn C++: Thám Hiểm Sao Hỏa

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const long long INF_MARS_LL = std::numeric_limits<long long>::max() / 2;
const int MAX_MARS_DIM = 105; // Max N, M dimensions
const int MAX_MARS_NODES = MAX_MARS_DIM * MAX_MARS_DIM * 2 + 5; // N*M*2 nodes + S + T

struct MarsEdge {
    int target_node;
    int next_edge_idx;
    long long flow_capacity;
    long long edge_cost;
};

MarsEdge mars_edges[MAX_MARS_NODES * 8]; // Max edges
int mars_head[MAX_MARS_NODES];
int mars_edge_counter = 1;

int max_paths_K, mars_cols, mars_rows; // k, m, n from problem
int cell_type[MAX_MARS_DIM][MAX_MARS_DIM]; // 0: empty, 1: obstacle, 2: rock

// Map (r, c)_in to node ID, (r, c)_out to node ID
int get_mars_in_node(int r, int c) { return (r - 1) * mars_cols + c; }
int get_mars_out_node(int r, int c) { return (r - 1) * mars_cols + c + mars_rows * mars_cols; }

int mars_source, mars_sink;

long long mars_min_cost_dist[MAX_MARS_NODES];
int mars_path_parent_nodes[MAX_MARS_NODES];
int mars_path_edge_indices[MAX_MARS_NODES];
bool mars_in_queue[MAX_MARS_NODES];

long long total_mars_flow = 0;
long long total_mars_min_cost = 0;

void add_mars_edge(int u, int v, long long capacity, long long cost) {
    mars_edges[++mars_edge_counter] = {v, mars_head[u], capacity, cost}; mars_head[u] = mars_edge_counter;
    mars_edges[++mars_edge_counter] = {u, mars_head[v], 0, -cost}; mars_head[v] = mars_edge_counter;
}

bool spfa_mars_shortest_path() {
    std::fill(mars_min_cost_dist, mars_min_cost_dist + mars_sink + 1, INF_MARS_LL);
    std::fill(mars_in_queue, mars_in_queue + mars_sink + 1, false);
    std::queue<int> q_spfa;

    mars_min_cost_dist[mars_source] = 0;
    q_spfa.push(mars_source);
    mars_in_queue[mars_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        mars_in_queue[u] = false;

        for (int i = mars_head[u]; i; i = mars_edges[i].next_edge_idx) {
            MarsEdge& edge = mars_edges[i];
            if (edge.flow_capacity > 0 && mars_min_cost_dist[edge.target_node] > mars_min_cost_dist[u] + edge.edge_cost) {
                mars_min_cost_dist[edge.target_node] = mars_min_cost_dist[u] + edge.edge_cost;
                mars_path_parent_nodes[edge.target_node] = u;
                mars_path_edge_indices[edge.target_node] = i;

                if (!mars_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    mars_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return mars_min_cost_dist[mars_sink] != INF_MARS_LL;
}

void find_min_cost_max_flow_mars() {
    total_mars_flow = 0;
    total_mars_min_cost = 0;
    while (spfa_mars_shortest_path()) {
        long long current_path_flow = INF_MARS_LL;

        for (int v = mars_sink; v != mars_source; v = mars_path_parent_nodes[v]) {
            int u = mars_path_parent_nodes[v];
            int edge_idx = mars_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, mars_edges[edge_idx].flow_capacity);
        }

        total_mars_flow += current_path_flow;
        total_mars_min_cost += current_path_flow * mars_min_cost_dist[mars_sink];

        for (int v = mars_sink; v != mars_source; v = mars_path_parent_nodes[v]) {
            int u = mars_path_parent_nodes[v];
            int edge_idx = mars_path_edge_indices[v];
            mars_edges[edge_idx].flow_capacity -= current_path_flow;
            mars_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

int paths_taken_through_cell[MAX_MARS_DIM][MAX_MARS_DIM]; // Tracks how many paths used a cell

void trace_mars_path(int r, int c, int path_id) {
    paths_taken_through_cell[r][c]--; // Decrement count for this cell
    if (r == mars_rows && c == mars_cols) return; // Reached destination

    // Try going down
    if (r + 1 <= mars_rows && paths_taken_through_cell[r + 1][c] > 0) {
        std::cout <> path_id << " " << 0 << '\n'; // 0 for Down
        trace_mars_path(r + 1, c, path_id);
        return;
    }
    // Try going right
    if (c + 1 <= mars_cols && paths_taken_through_cell[r][c + 1] > 0) {
        std::cout <> path_id << " " << 1 << '\n'; // 1 for Right
        trace_mars_path(r, c + 1, path_id);
        return;
    }
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> max_paths_K >> mars_cols >> mars_rows;

    // Node IDs: (r, c)_in maps to (r-1)*mars_cols + c
    // (r, c)_out maps to (r-1)*mars_cols + c + mars_rows*mars_cols
    int num_grid_nodes = mars_rows * mars_cols;
    mars_source = 0;
    mars_sink = num_grid_nodes * 2 + 1;

    for (int i = 1; i <= mars_rows; ++i) {
        for (int j = 1; j <= mars_cols; ++j) {
            std::cin >> cell_type[i][j];
        }
    }

    add_mars_edge(mars_source, get_mars_in_node(1, 1), max_paths_K, 0); // K paths start at (1,1)
    add_mars_edge(get_mars_out_node(mars_rows, mars_cols), mars_sink, max_paths_K, 0); // K paths end at (N,M)

    for (int r = 1; r <= mars_rows; ++r) {
        for (int c = 1; c <= mars_cols; ++c) {
            int in_node = get_mars_in_node(r, c);
            int out_node = get_mars_out_node(r, c);

            if (cell_type[r][c] == 1) continue; // Obstacle, no path through

            // Edge for collecting rock if available
            if (cell_type[r][c] == 2) { // Has a rock
                add_mars_edge(in_node, out_node, 1, -1); // Capacity 1, cost -1 for collecting rock
            }
            add_mars_edge(in_node, out_node, INF_MARS_LL, 0); // Infinite capacity, cost 0 for simply passing through

            // Edges for moving down
            if (r + 1 <= mars_rows && cell_type[r + 1][c] != 1) { // If not an obstacle below
                add_mars_edge(out_node, get_mars_in_node(r + 1, c), INF_MARS_LL, 0);
            }
            // Edges for moving right
            if (c + 1 <= mars_cols && cell_type[r][c + 1] != 1) { // If not an obstacle to the right
                add_mars_edge(out_node, get_mars_in_node(r, c + 1), INF_MARS_LL, 0);
            }
        }
    }

    find_min_cost_max_flow_mars();

    // Reconstruct paths from residual graph
    // Find how many times each cell's 'collect rock' or 'pass through' edge was used
    for (int r = 1; r <= mars_rows; ++r) {
        for (int c = 1; c <= mars_cols; ++c) {
            int in_node = get_mars_in_node(r, c);
            int out_node = get_mars_out_node(r, c);
            for (int i = mars_head[in_node]; i; i = mars_edges[i].next_edge_idx) {
                if (mars_edges[i].target_node == out_node) {
                    if (mars_edges[i].edge_cost == -1) { // Rock collection edge
                        paths_taken_through_cell[r][c] += 1 - mars_edges[i].flow_capacity; // flow = initial_cap - residual_cap
                    } else { // Pass through edge
                        paths_taken_through_cell[r][c] += INF_MARS_LL - mars_edges[i].flow_capacity; // How much flow passed
                    }
                }
            }
        }
    }
    
    // For path reconstruction, initial and final cells need to count all K paths
    paths_taken_through_cell[1][1] = max_paths_K;
    paths_taken_through_cell[mars_rows][mars_cols] = max_paths_K;

    for (int i = 1; i <= max_paths_K; ++i) {
        trace_mars_path(1, 1, i);
    }

    return 0;
}

Bài Toán Tập Hợp Đoạn Thẳng K-Lặp Lại Dài Nhất

Bài toán này yêu cầu chọn một tập hợp các đoạn thẳng (segments) trên mặt phẳng sao cho bất kỳ điểm nào trên trục x không bị bao phủ bởi quá K đoạn thẳng, và tổng chiều dài của các đoạn thẳng được chọn là lớn nhất. Đây là một bài toán mô hình lựa chọn khoảng (Interval Selection) có thể giải bằng Min-Cost Max-Flow với kỹ thuật nén tọa độ.

Kỹ thuật nén tọa độ là cần thiết vì các tọa độ có thể rất lớn, nhưng chỉ có các điểm cuối của các đoạn thẳng là quan trọng. Sau khi nén tọa độ, ta tạo một đồ thị trên các điểm nén này.

Mô hình đồ thị:

• Thu thập tất cả các điểm đầu và điểm cuối của các đoạn thẳng, sau đó nén tọa độ để có các điểm duy nhất từ 1 đến num_unique_points.
• Tạo một nút nguồn S và một nút đích T.
• Đối với mỗi điểm nén i đến i+1, thêm một cạnh từ i đến i+1 với dung lượng K và chi phí 0. Đây là dung lượng cho phép K đoạn thẳng đi qua khoảng giữa i và i+1.
• Đối với mỗi đoạn thẳng gốc [L, R] có chiều dài len, thêm một cạnh từ nút nén L đến nút nén R với dung lượng 1 và chi phí -len (để tối đa hóa tổng chiều dài).

Min-Cost Max-Flow trên đồ thị này sẽ tìm ra tập hợp các đoạn thẳng tối ưu. Lưu ý rằng các đoạn thẳng có thể có cùng tọa độ x, tạo thành các đoạn thẳng dọc. Việc mở rộng tọa độ có thể giúp phân biệt chúng.

Mã Nguồn C++: Tập Hợp Đoạn Thẳng K-Lặp Lại Dài Nhất

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;cmath> // For sqrt
#lt;limits>

const long long INF_SEG_LL = std::numeric_limits<long long>::max() / 2;
const int MAX_SEG_COUNT = 5005; // Max N segments
const int MAX_COMPRESSED_POINTS = MAX_SEG_COUNT * 2 + 5; // Max 2N unique points + S + T

struct SegmentEdge {
    int target_node;
    int next_edge_idx;
    long long flow_capacity;
    long long edge_cost;
};

SegmentEdge seg_edges[MAX_COMPRESSED_POINTS * 10]; // Max edges
int seg_head[MAX_COMPRESSED_POINTS];
int seg_edge_counter = 1;

int num_segments, max_overlap_K;
int segment_start_idx[MAX_SEG_COUNT], segment_end_idx[MAX_SEG_COUNT];
long long segment_lengths[MAX_SEG_COUNT];

int unique_coordinates[MAX_COMPRESSED_POINTS];
int unique_coords_count = 0;

int seg_source, seg_sink;

long long seg_min_cost_dist[MAX_COMPRESSED_POINTS];
int seg_path_parent_nodes[MAX_COMPRESSED_POINTS];
int seg_path_edge_indices[MAX_COMPRESSED_POINTS];
bool seg_in_queue[MAX_COMPRESSED_POINTS];

long long total_seg_flow = 0;
long long total_seg_min_cost = 0;

void add_seg_edge(int u, int v, long long capacity, long long cost) {
    seg_edges[++seg_edge_counter] = {v, seg_head[u], capacity, cost}; seg_head[u] = seg_edge_counter;
    seg_edges[++seg_edge_counter] = {u, seg_head[v], 0, -cost}; seg_head[v] = seg_edge_counter;
}

bool spfa_seg_shortest_path() {
    std::fill(seg_min_cost_dist, seg_min_cost_dist + seg_sink + 1, INF_SEG_LL);
    std::fill(seg_in_queue, seg_in_queue + seg_sink + 1, false);
    std::queue<int> q_spfa;

    seg_min_cost_dist[seg_source] = 0;
    q_spfa.push(seg_source);
    seg_in_queue[seg_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        seg_in_queue[u] = false;

        for (int i = seg_head[u]; i; i = seg_edges[i].next_edge_idx) {
            SegmentEdge& edge = seg_edges[i];
            if (edge.flow_capacity > 0 && seg_min_cost_dist[edge.target_node] > seg_min_cost_dist[u] + edge.edge_cost) {
                seg_min_cost_dist[edge.target_node] = seg_min_cost_dist[u] + edge.edge_cost;
                seg_path_parent_nodes[edge.target_node] = u;
                seg_path_edge_indices[edge.target_node] = i;

                if (!seg_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    seg_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return seg_min_cost_dist[seg_sink] != INF_SEG_LL;
}

void find_min_cost_max_flow_segment() {
    total_seg_flow = 0;
    total_seg_min_cost = 0;
    while (spfa_seg_shortest_path()) {
        long long current_path_flow = INF_SEG_LL;

        for (int v = seg_sink; v != seg_source; v = seg_path_parent_nodes[v]) {
            int u = seg_path_parent_nodes[v];
            int edge_idx = seg_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, seg_edges[edge_idx].flow_capacity);
        }

        total_seg_flow += current_path_flow;
        total_seg_min_cost += current_path_flow * seg_min_cost_dist[seg_sink];

        for (int v = seg_sink; v != seg_source; v = seg_path_parent_nodes[v]) {
            int u = seg_path_parent_nodes[v];
            int edge_idx = seg_path_edge_indices[v];
            seg_edges[edge_idx].flow_capacity -= current_path_flow;
            seg_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_segments >> max_overlap_K;

    std::vector<long long> raw_coords;

    for (int i = 1; i <= num_segments; ++i) {
        long long x1, y1, x2, y2;
        std::cin >> x1 >> y1 >> x2 >> y2;

        if (x1 > x2) { // Ensure x1 <= x2
            std::swap(x1, x2);
            std::swap(y1, y2);
        }
        segment_lengths[i] = static_cast<long long>(std::sqrt( (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) ));

        // Coordinate transformation for handling vertical segments and overlap logic
        // If x1 == x2 (vertical segment), map to [2x1, 2x1+1] effectively
        // If x1 != x2 (horizontal/diagonal), map to [2x1+1, 2x2] to prevent overlap at endpoints
        x1 *= 2; x2 *= 2;
        if (x1 == x2) { // Vertical segment
            segment_start_idx[i] = x1;
            segment_end_idx[i] = x2 + 1; // [2x, 2x+1]
        } else { // Non-vertical segment
            segment_start_idx[i] = x1 + 1;
            segment_end_idx[i] = x2; // (2x1, 2x2) -> [2x1+1, 2x2]
        }
        raw_coords.push_back(segment_start_idx[i]);
        raw_coords.push_back(segment_end_idx[i]);
    }

    // Coordinate compression
    std::sort(raw_coords.begin(), raw_coords.end());
    raw_coords.erase(std::unique(raw_coords.begin(), raw_coords.end()), raw_coords.end());
    
    unique_coords_count = raw_coords.size();
    for(int i = 0; i < unique_coords_count; ++i) unique_coordinates[i+1] = raw_coords[i]; // Store original values

    seg_source = 0;
    seg_sink = unique_coords_count + 1; // Nodes are 1 to unique_coords_count

    // Edges between consecutive compressed points
    for (int i = 1; i < unique_coords_count; ++i) {
        add_seg_edge(i, i + 1, max_overlap_K, 0); // Capacity K, cost 0
    }

    // Add edges for each segment
    for (int i = 1; i <= num_segments; ++i) {
        int u_comp = std::lower_bound(raw_coords.begin(), raw_coords.end(), segment_start_idx[i]) - raw_coords.begin() + 1;
        int v_comp = std::lower_bound(raw_coords.begin(), raw_coords.end(), segment_end_idx[i]) - raw_coords.begin() + 1;
        add_seg_edge(u_comp, v_comp, 1, -segment_lengths[i]); // Capacity 1, cost -length
    }

    // Connect virtual source and sink
    add_seg_edge(seg_source, 1, max_overlap_K, 0);
    add_seg_edge(unique_coords_count, seg_sink, max_overlap_K, 0);
    
    find_min_cost_max_flow_segment();

    std::cout <> -total_seg_min_cost << std::endl;

    return 0;
}

Bài Toán Tập Hợp Khoảng K-Lặp Lại Dài Nhất

Bài toán này tương tự bài toán Tập Hợp Đoạn Thẳng K-Lặp Lại Dài Nhất, nhưng chỉ xét các khoảng trên trục số. Yêu cầu chọn một tập hợp các khoảng (intervals) sao cho bất kỳ điểm nào trên trục x không bị bao phủ bởi quá K khoảng, và tổng chiều dài của các khoảng được chọn là lớn nhất. Đây cũng là một bài toán mô hình lựa chọn khoảng có thể giải bằng Min-Cost Max-Flow với kỹ thuật nén tọa độ.

Mô hình đồ thị:

• Thu thập tất cả các điểm đầu và điểm cuối của các khoảng, sau đó nén tọa độ để có các điểm duy nhất từ 1 đến num_unique_points.
• Tạo một nút nguồn S và một nút đích T.
• Đối với mỗi điểm nén i đến i+1, thêm một cạnh từ i đến i+1 với dung lượng K và chi phí 0.
• Đối với mỗi khoảng gốc [L, R] có chiều dài len, thêm một cạnh từ nút nén L đến nút nén R với dung lượng 1 và chi phí -len.
• Thêm các cạnh từ S đến điểm nén đầu tiên và từ điểm nén cuối cùng đến T, đều có dung lượng K và chi phí 0, để cho phép K đường đi (tức là K khoảng) đi qua toàn bộ trục số.

Min-Cost Max-Flow sẽ tối đa hóa tổng chiều dài của các khoảng được chọn.

Mã Nguồn C++: Tập Hợp Khoảng K-Lặp Lại Dài Nhất

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const long long INF_INTERVAL_LL = std::numeric_limits<long long>::max() / 2;
const int MAX_INTERVAL_COUNT = 1005; // Max N intervals
const int MAX_COMPRESSED_INTERVAL_POINTS = MAX_INTERVAL_COUNT * 2 + 5; // Max 2N unique points + S + T

struct IntervalEdge {
    int target_node;
    int next_edge_idx;
    long long flow_capacity;
    long long edge_cost;
};

IntervalEdge interval_edges[MAX_COMPRESSED_INTERVAL_POINTS * 5]; // Max edges (approx 2N edges + N segments)
int interval_head[MAX_COMPRESSED_INTERVAL_POINTS];
int interval_edge_counter = 1;

int num_intervals, max_interval_overlap_K;
int interval_raw_starts[MAX_INTERVAL_COUNT], interval_raw_ends[MAX_INTERVAL_COUNT];

long long unique_interval_coords[MAX_COMPRESSED_INTERVAL_POINTS];
int unique_interval_coords_count = 0;

int interval_source, interval_sink;

long long interval_min_cost_dist[MAX_COMPRESSED_INTERVAL_POINTS];
int interval_path_parent_nodes[MAX_COMPRESSED_INTERVAL_POINTS];
int interval_path_edge_indices[MAX_COMPRESSED_INTERVAL_POINTS];
bool interval_in_queue[MAX_COMPRESSED_INTERVAL_POINTS];

long long total_interval_flow = 0;
long long total_interval_min_cost = 0;

void add_interval_edge(int u, int v, long long capacity, long long cost) {
    interval_edges[++interval_edge_counter] = {v, interval_head[u], capacity, cost}; interval_head[u] = interval_edge_counter;
    interval_edges[++interval_edge_counter] = {u, interval_head[v], 0, -cost}; interval_head[v] = interval_edge_counter;
}

bool spfa_interval_shortest_path() {
    std::fill(interval_min_cost_dist, interval_min_cost_dist + interval_sink + 1, INF_INTERVAL_LL);
    std::fill(interval_in_queue, interval_in_queue + interval_sink + 1, false);
    std::queue<int> q_spfa;

    interval_min_cost_dist[interval_source] = 0;
    q_spfa.push(interval_source);
    interval_in_queue[interval_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        interval_in_queue[u] = false;

        for (int i = interval_head[u]; i; i = interval_edges[i].next_edge_idx) {
            IntervalEdge& edge = interval_edges[i];
            if (edge.flow_capacity > 0 && interval_min_cost_dist[edge.target_node] > interval_min_cost_dist[u] + edge.edge_cost) {
                interval_min_cost_dist[edge.target_node] = interval_min_cost_dist[u] + edge.edge_cost;
                interval_path_parent_nodes[edge.target_node] = u;
                interval_path_edge_indices[edge.target_node] = i;

                if (!interval_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    interval_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return interval_min_cost_dist[interval_sink] != INF_INTERVAL_LL;
}

void find_min_cost_max_flow_interval() {
    total_interval_flow = 0;
    total_interval_min_cost = 0;
    while (spfa_interval_shortest_path()) {
        long long current_path_flow = INF_INTERVAL_LL;

        for (int v = interval_sink; v != interval_source; v = interval_path_parent_nodes[v]) {
            int u = interval_path_parent_nodes[v];
            int edge_idx = interval_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, interval_edges[edge_idx].flow_capacity);
        }

        total_interval_flow += current_path_flow;
        total_interval_min_cost += current_path_flow * interval_min_cost_dist[interval_sink];

        for (int v = interval_sink; v != interval_source; v = interval_path_parent_nodes[v]) {
            int u = interval_path_parent_nodes[v];
            int edge_idx = interval_path_edge_indices[v];
            interval_edges[edge_idx].flow_capacity -= current_path_flow;
            interval_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_intervals >> max_interval_overlap_K;

    std::vector<long long> raw_interval_coords;

    for (int i = 1; i <= num_intervals; ++i) {
        std::cin >> interval_raw_starts[i] >> interval_raw_ends[i];
        raw_interval_coords.push_back(interval_raw_starts[i]);
        raw_interval_coords.push_back(interval_raw_ends[i]);
    }
    
    // Add implicit boundary points to cover entire range, e.g., 1 and 10^5
    raw_interval_coords.push_back(1);
    raw_interval_coords.push_back(100000);

    // Coordinate compression
    std::sort(raw_interval_coords.begin(), raw_interval_coords.end());
    raw_interval_coords.erase(std::unique(raw_interval_coords.begin(), raw_interval_coords.end()), raw_interval_coords.end());
    
    unique_interval_coords_count = raw_interval_coords.size();
    for(int i = 0; i < unique_interval_coords_count; ++i) unique_interval_coords[i+1] = raw_interval_coords[i];

    interval_source = 0;
    interval_sink = unique_interval_coords_count + 1; // Nodes are 1 to unique_interval_coords_count

    // Edges between consecutive compressed points
    for (int i = 1; i < unique_interval_coords_count; ++i) {
        add_interval_edge(i, i + 1, max_interval_overlap_K, 0); // Capacity K, cost 0
    }

    // Connect virtual source and sink to global boundaries
    add_interval_edge(interval_source, 1, max_interval_overlap_K, 0);
    add_interval_edge(unique_interval_coords_count, interval_sink, max_interval_overlap_K, 0);

    // Add edges for each interval
    for (int i = 1; i <= num_intervals; ++i) {
        int u_comp = std::lower_bound(raw_interval_coords.begin(), raw_interval_coords.end(), interval_raw_starts[i]) - raw_interval_coords.begin() + 1;
        int v_comp = std::lower_bound(raw_interval_coords.begin(), raw_interval_coords.end(), interval_raw_ends[i]) - raw_interval_coords.begin() + 1;
        long long length = unique_interval_coords[v_comp] - unique_interval_coords[u_comp];
        add_interval_edge(u_comp, v_comp, 1, -length); // Capacity 1, cost -length
    }
    
    find_min_cost_max_flow_interval();

    std::cout <> -total_interval_min_cost << std::endl;

    return 0;
}

Bài Toán Lái Xe Tiếp Nhiên Liệu

Đây là một bài toán đường đi ngắn nhất (shortest path) trên đồ thị phân tầng (layered graph). Trạng thái của xe không chỉ phụ thuộc vào vị trí (x, y) mà còn vào lượng nhiên liệu còn lại trong bình. Do đó, ta cần tạo các nút cho từng trạng thái (x, y, nhiên_liệu_còn_lại).

Mô hình đồ thị:

• Mỗi nút là một bộ ba (r, c, fuel), trong đó (r, c) là tọa độ ô vuông và fuel là lượng nhiên liệu còn lại.
• Các cạnh nối các trạng thái:
  • Di chuyển: Từ (r, c, fuel) đến (r', c', fuel-1) với chi phí di chuyển (nếu (r', c') là ô trống) hoặc chi phí di chuyển + chi phí đổ xăng (nếu (r', c') là trạm xăng).
  • Đổ xăng: Từ (r, c, fuel) đến (r, c, max_fuel) với chi phí đổ xăng.

Sử dụng thuật toán Dijkstra (với hàng đợi ưu tiên) để tìm đường đi ngắn nhất từ trạng thái ban đầu (1, 1, max_fuel) đến bất kỳ trạng thái nào có tọa độ (N, N).

Mã Nguồn C++: Lái Xe Tiếp Nhiên Liệu

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const int INF_FUEL_COST = std::numeric_limits<int>::max() / 2;
const int MAX_FUEL_DIM = 105; // Max N dimension
const int MAX_FUEL_TANK = 15; // Max M fuel capacity
const int MAX_FUEL_NODES = MAX_FUEL_DIM * MAX_FUEL_DIM * MAX_FUEL_TANK + 5; // N*N*M nodes

struct FuelEdge {
    int target_state_id;
    int edge_weight;
};

std::vector<FuelEdge> fuel_adjacency_list[MAX_FUEL_NODES];

int board_dim, max_fuel_capacity, refill_cost, move_cost, stay_refill_cost; // N, M, A, B, C from problem
bool is_refuel_station[MAX_FUEL_DIM][MAX_FUEL_DIM]; // True if (r, c) is a refuel station

// Map (row, col, fuel_left) to a unique state ID
inline int get_fuel_state_id(int r, int c, int fuel_left) {
    return ((r - 1) * board_dim + (c - 1)) * (max_fuel_capacity + 1) + fuel_left;
}

int min_fuel_costs[MAX_FUEL_NODES];
bool fuel_state_visited[MAX_FUEL_NODES];

struct FuelNode {
    int state_id;
    int current_cost;

    bool operator<(const FuelNode& other) const {
        return current_cost > other.current_cost;
    }
};

void dijkstra_fuel_problem() {
    std::fill(min_fuel_costs, min_fuel_costs + MAX_FUEL_NODES, INF_FUEL_COST);
    std::fill(fuel_state_visited, fuel_state_visited + MAX_FUEL_NODES, false);
    std::priority_queue<FuelNode> pq;

    int initial_state_id = get_fuel_state_id(1, 1, max_fuel_capacity);
    min_fuel_costs[initial_state_id] = 0;
    pq.push({initial_state_id, 0});

    while (!pq.empty()) {
        FuelNode current = pq.top();
        pq.pop();

        int u_state_id = current.state_id;
        int u_cost = current.current_cost;

        if (fuel_state_visited[u_state_id]) continue;
        fuel_state_visited[u_state_id] = true;

        for (const auto& edge : fuel_adjacency_list[u_state_id]) {
            int v_state_id = edge.target_state_id;
            int edge_weight = edge.edge_weight;
            if (min_fuel_costs[v_state_id] > u_cost + edge_weight) {
                min_fuel_costs[v_state_id] = u_cost + edge_weight;
                pq.push({v_state_id, min_fuel_costs[v_state_id]});
            }
        }
    }
}

int dr[] = {-1, 1, 0, 0}; // Up, Down
int dc[] = {0, 0, -1, 1}; // Left, Right

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> board_dim >> max_fuel_capacity >> refill_cost >> move_cost >> stay_refill_cost;

    for (int r = 1; r <= board_dim; ++r) {
        for (int c = 1; c <= board_dim; ++c) {
            std::cin >> is_refuel_station[r][c];
        }
    }

    for (int r = 1; r <= board_dim; ++r) {
        for (int c = 1; c <= board_dim; ++c) {
            // Option 1: Refuel at current station (if it's one)
            // Any amount of fuel to max_fuel_capacity, cost is 'A + C' (A for refilling, C for staying)
            // The problem statement logic is slightly ambiguous for 'C' cost for staying.
            // If it's a refuel station, you can refuel up to full for cost A.
            // Original code adds (get(i,j,0), get(i,j,m), A+C), and (get(i,j,k), get(i,j,m), A+C)
            // This means from ANY fuel level, you can choose to refuel to MAX_FUEL for cost A + C.
            // Let's follow this.
            for (int fuel_left = 0; fuel_left <= max_fuel_capacity; ++fuel_left) {
                 if (is_refuel_station[r][c]) {
                    if (fuel_left < max_fuel_capacity) { // Only if not already full
                        fuel_adjacency_list[get_fuel_state_id(r, c, fuel_left)].push_back({get_fuel_state_id(r, c, max_fuel_capacity), refill_cost + stay_refill_cost});
                    }
                }
            }


            // Option 2: Move to adjacent cells
            for (int fuel_left = 1; fuel_left <= max_fuel_capacity; ++fuel_left) { // Need at least 1 fuel to move
                for (int d = 0; d < 4; ++d) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];

                    if (nr >= 1 && nr <= board_dim && nc >= 1 && nc <= board_dim) {
                        int move_cost_actual = move_cost;
                        // Problem states "moving to a cell from (i,j) to (i',j') if i'>i or j'>j cost B"
                        // This implies moving 'down' or 'right' costs B, 'up' or 'left' costs 0.
                        // The problem statement implies B is added only if moving to a "smaller" coordinate (i.e. to left or up).
                        // Original code: if x<i or y<j (new x/y is smaller than current) then val = B. This means (r,c) to (nr,nc)
                        // if nr < r or nc < c.
                        if (nr < r || nc < c) { // Moving "backwards" (up or left)
                             move_cost_actual += move_cost; // This logic is confusing, original code 'val=B' then 'val+A' or 'val'. Let's simplify.
                                                           // Original: `if (x<i||y<j) val=b;` and then `val+a` or `val`.
                                                           // This indicates `move_cost` is 0 by default, `B` if moving "backwards".
                                                           // My `move_cost` is a fixed B.
                                                           // Let's re-interpret: Base move cost is 0. Penalty B for certain moves.
                                                           // Cost A is for refilling. Cost C is for staying at refilling station.
                                                           // The example code means:
                                                           //   - Movement base cost: 0
                                                           //   - If moving backwards (nr<r || nc<c): add B.
                                                           //   - If target cell is refuel station: add A (for refilling).
                                                           // This interpretation matches `val=0` then `val=B` and `val+A`.
                                                           // Let's re-align to problem text A, B, C:
                                                           // A: cost to refuel (any amount to full)
                                                           // B: cost for moving to an *already visited* cell. This implies a specific kind of 'backwards' move.
                                                           //    The example code simplifies it to 'moving to a smaller coordinate'.
                                                           // C: cost to stay at a refuel station.

                                                           // Re-interpreting for clarity to my variable names:
                                                           // `refill_cost` = A
                                                           // `move_cost` = B
                                                           // `stay_refill_cost` = C

                                                           // Cost for moving to (nr, nc) from (r, c):
                                                           //   - Base cost: 0
                                                           //   - If (nr < r OR nc < c): add `move_cost` (B)
                                                           //   - If `is_refuel_station[nr][nc]` AND you refuel at `(nr, nc)`: add `refill_cost` (A)
                                                           //   - If `is_refuel_station[r][c]` AND you refuel at `(r, c)`: add `stay_refill_cost` (C)

                                                           // This is getting complex. The original C++ provided a specific graph construction.
                                                           // Let's stick to the graph construction implied by the original code.
                                                           // Original edge: `add(get(i,j,k),get(x,y,m),val+a)` where val is 0 or B, a is `refill_cost`
                                                           // means: if (x,y) is refuel station, move there and refuel to full: cost (0 or B) + A.
                                                           // Original edge: `add(get(i,j,k),get(x,y,k-1),val)` where val is 0 or B.
                                                           // means: if (x,y) is NOT refuel station, move there (fuel-1): cost (0 or B).

                             move_cost_actual = move_cost; // Let's use B for 'backward' move penalty
                        } else {
                            move_cost_actual = 0; // No penalty for 'forward' move
                        }


                        if (is_refuel_station[nr][nc]) { // Move to a refuel station and refuel
                            fuel_adjacency_list[get_fuel_state_id(r, c, fuel_left)].push_back({get_fuel_state_id(nr, nc, max_fuel_capacity), move_cost_actual + refill_cost});
                        } else { // Move to a non-refuel station
                            fuel_adjacency_list[get_fuel_state_id(r, c, fuel_left)].push_back({get_fuel_state_id(nr, nc, fuel_left - 1), move_cost_actual});
                        }
                    }
                }
            }
        }
    }

    dijkstra_fuel_problem();

    int min_total_cost = INF_FUEL_COST;
    for (int fuel_left = 0; fuel_left &lt;= max_fuel_capacity; ++fuel_left) {
        min_total_cost = std::min(min_total_cost, min_fuel_costs[get_fuel_state_id(board_dim, board_dim, fuel_left)]);
    }

    std::cout &lt;&gt; min_total_cost &lt;&lt; std::endl;

    return 0;
}
</code>

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>

const int MAX_ISLAND_DIM = 11; // Max N, M dimensions
const int MAX_KEYS = 11; // Max T keys
const int MAX_KEY_MASK = 1 << MAX_KEYS; // 2^T states for keys

// dr, dc for 4 directions: Up, Right, Down, Left
int dr_island[] = {-1, 0, 1, 0};
int dc_island[] = {0, 1, 0, -1};

// Stores required keys to pass a door: door_keys[r][c][direction_idx]
int required_door_keys[MAX_ISLAND_DIM][MAX_ISLAND_DIM][4];
// Stores keys present at cell: cell_keys[r][c]
int cell_keys_present[MAX_ISLAND_DIM][MAX_ISLAND_DIM];

struct IslandState {
    int row, col;
    int key_mask;
    int steps;
};

bool island_visited[MAX_ISLAND_DIM][MAX_ISLAND_DIM][MAX_KEY_MASK];

int island_rows, island_cols, total_keys_count, num_doors, num_keys_on_cells; // N, M, T, K, S from problem

// Helper to build required_door_keys for both directions
void build_door_info(int r1, int c1, int r2, int c2, int key_needed) {
    for (int i = 0; i < 4; ++i) {
        if (r1 + dr_island[i] == r2 && c1 + dc_island[i] == c2) {
            required_door_keys[r1][c1][i] |= (1 << key_needed);
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> island_rows >> island_cols >> total_keys_count >> num_doors;

    for (int i = 0; i < num_doors; ++i) {
        int r1, c1, r2, c2, key_val;
        std::cin >> r1 >> c1 >> r2 >> c2 >> key_val;
        build_door_info(r1, c1, r2, c2, key_val);
        build_door_info(r2, c2, r1, c1, key_val); // Doors are bidirectional
    }

    std::cin >> num_keys_on_cells;
    for (int i = 0; i < num_keys_on_cells; ++i) {
        int r, c, key_val;
        std::cin >> r >> c >> key_val;
        cell_keys_present[r][c] |= (1 << key_val);
    }

    std::queue<IslandState> q_bfs;

    // Initial state: (1,1) with keys collected at (1,1)
    int initial_keys = cell_keys_present[1][1];
    q_bfs.push({1, 1, initial_keys, 0});
    island_visited[1][1][initial_keys] = true;

    while (!q_bfs.empty()) {
        IslandState current = q_bfs.front();
        q_bfs.pop();

        if (current.row == island_rows && current.col == island_cols) {
            std::cout <> current.steps << std::endl;
            return 0;
        }

        for (int i = 0; i < 4; ++i) {
            // Check if current keys can open the door
            if (((current.key_mask | required_door_keys[current.row][current.col][i]) != current.key_mask)) {
                continue; // Cannot pass this door, missing keys
            }

            int next_r = current.row + dr_island[i];
            int next_c = current.col + dc_island[i];

            // Check boundary conditions
            if (next_r < 1 || next_r > island_rows || next_c < 1 || next_c > island_cols) {
                continue;
            }

            // New key mask after visiting next cell
            int next_key_mask = current.key_mask | cell_keys_present[next_r][next_c];

            if (!island_visited[next_r][next_c][next_key_mask]) {
                island_visited[next_r][next_c][next_key_mask] = true;
                q_bfs.push({next_r, next_c, next_key_mask, current.steps + 1});
            }
        }
    }

    std::cout <> -1 << std::endl; // No solution
    return 0;
}

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const long long INF_ROBOT_LL = std::numeric_limits<long long>::max() / 2;
const int MAX_ROBOT_GRID_DIM = 65; // Max N, M (problem statement says 50, 60, N, M are rows/cols)
const int MAX_ROBOT_NODES = MAX_ROBOT_GRID_DIM * MAX_ROBOT_GRID_DIM * 2 + 5; // N*M*2 nodes + S + T

struct RobotEdge {
    int target_node;
    int next_edge_idx;
    long long flow_capacity;
    long long edge_cost;
};

RobotEdge robot_edges[MAX_ROBOT_NODES * 8]; // Max edges
int robot_head[MAX_ROBOT_NODES];
int robot_edge_counter = 1;

int num_start_points, num_end_points, grid_rows_robot, grid_cols_robot; // A, B, N, M from problem

// Map (r, c) to (r, c)_in and (r, c)_out node IDs
inline int get_robot_in_node(int r, int c) { return r * (grid_cols_robot + 1) + c; }
inline int get_robot_out_node(int r, int c) { return r * (grid_cols_robot + 1) + c + (grid_rows_robot + 1) * (grid_cols_robot + 1); }

int robot_source, robot_sink;

long long robot_min_cost_dist[MAX_ROBOT_NODES];
int robot_path_parent_nodes[MAX_ROBOT_NODES];
int robot_path_edge_indices[MAX_ROBOT_NODES];
bool robot_in_queue[MAX_ROBOT_NODES];

long long total_robot_flow = 0;
long long total_robot_min_cost = 0;

void add_robot_edge(int u, int v, long long capacity, long long cost) {
    robot_edges[++robot_edge_counter] = {v, robot_head[u], capacity, cost}; robot_head[u] = robot_edge_counter;
    robot_edges[++robot_edge_counter] = {u, robot_head[v], 0, -cost}; robot_head[v] = robot_edge_counter;
}

bool spfa_robot_shortest_path() {
    std::fill(robot_min_cost_dist, robot_min_cost_dist + robot_sink + 1, INF_ROBOT_LL);
    std::fill(robot_in_queue, robot_in_queue + robot_sink + 1, false);
    std::queue<int> q_spfa;

    robot_min_cost_dist[robot_source] = 0;
    q_spfa.push(robot_source);
    robot_in_queue[robot_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        robot_in_queue[u] = false;

        for (int i = robot_head[u]; i; i = robot_edges[i].next_edge_idx) {
            RobotEdge& edge = robot_edges[i];
            if (edge.flow_capacity > 0 && robot_min_cost_dist[edge.target_node] > robot_min_cost_dist[u] + edge.edge_cost) {
                robot_min_cost_dist[edge.target_node] = robot_min_cost_dist[u] + edge.edge_cost;
                robot_path_parent_nodes[edge.target_node] = u;
                robot_path_edge_indices[edge.target_node] = i;

                if (!robot_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    robot_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return robot_min_cost_dist[robot_sink] != INF_ROBOT_LL;
}

void find_min_cost_max_flow_robot() {
    total_robot_flow = 0;
    total_robot_min_cost = 0;
    while (spfa_robot_shortest_path()) {
        long long current_path_flow = INF_ROBOT_LL;

        for (int v = robot_sink; v != robot_source; v = robot_path_parent_nodes[v]) {
            int u = robot_path_parent_nodes[v];
            int edge_idx = robot_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, robot_edges[edge_idx].flow_capacity);
        }

        total_robot_flow += current_path_flow;
        total_robot_min_cost += current_path_flow * robot_min_cost_dist[robot_sink];

        for (int v = robot_sink; v != robot_source; v = robot_path_parent_nodes[v]) {
            int u = robot_path_parent_nodes[v];
            int edge_idx = robot_path_edge_indices[v];
            robot_edges[edge_idx].flow_capacity -= current_path_flow;
            robot_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_start_points >> num_end_points >> grid_rows_robot >> grid_cols_robot;

    // Node IDs for (r, c): 0-indexed (r, c). Max r is N, max c is M.
    // The nodes are (0,0) to (N,M).
    // The original code uses N and M as N_rows, M_cols
    // So nodes (i,j) where i from 0 to N, j from 0 to M.
    // (grid_rows_robot+1) * (grid_cols_robot+1) nodes for in-nodes, same for out-nodes.
    int max_node_id_val = (grid_rows_robot + 1) * (grid_cols_robot + 1) * 2 + 1;
    robot_source = 0;
    robot_sink = max_node_id_val;

    // Add edges for horizontal movements (j to j+1)
    for (int i = 0; i <= grid_rows_robot; ++i) { // Row i
        for (int j = 0; j < grid_cols_robot; ++j) { // Column j to j+1
            long long weight;
            std::cin >> weight;
            add_robot_edge(get_robot_out_node(i, j), get_robot_in_node(i, j + 1), 1, -weight);
            add_robot_edge(get_robot_out_node(i, j), get_robot_in_node(i, j + 1), INF_ROBOT_LL, 0);
        }
    }

    // Add edges for vertical movements (i to i+1)
    for (int j = 0; j <= grid_cols_robot; ++j) { // Column j
        for (int i = 0; i < grid_rows_robot; ++i) { // Row i to i+1
            long long weight;
            std::cin >> weight;
            add_robot_edge(get_robot_out_node(i, j), get_robot_in_node(i + 1, j), 1, -weight);
            add_robot_edge(get_robot_out_node(i, j), get_robot_in_node(i + 1, j), INF_ROBOT_LL, 0);
        }
    }

    // Connect in-node to out-node for each grid cell
    for (int i = 0; i <= grid_rows_robot; ++i) {
        for (int j = 0; j <= grid_cols_robot; ++j) {
            add_robot_edge(get_robot_in_node(i, j), get_robot_out_node(i, j), INF_ROBOT_LL, 0);
        }
    }

    // Connect source to start points
    for (int i = 0; i < num_start_points; ++i) {
        int k_robots, r, c;
        std::cin >> k_robots >> r >> c;
        add_robot_edge(robot_source, get_robot_in_node(r, c), k_robots, 0);
    }

    // Connect end points to sink
    for (int i = 0; i < num_end_points; ++i) {
        int k_robots, r, c;
        std::cin >> k_robots >> r >> c;
        add_robot_edge(get_robot_out_node(r, c), robot_sink, k_robots, 0);
    }

    find_min_cost_max_flow_robot();

    std::cout <> -total_robot_min_cost << std::endl;

    return 0;
}

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const long long INF_TRAPEZOID_LL = std::numeric_limits<long long>::max() / 2;
const int MAX_TRAPEZOID_DIM = 55; // Max M, N dimensions
const int MAX_TRAPEZOID_NODES = MAX_TRAPEZOID_DIM * MAX_TRAPEZOID_DIM * 2 + 5; // (N+M)*2 nodes + S + T

struct TrapezoidEdge {
    int target_node;
    int next_edge_idx;
    long long flow_capacity;
    long long edge_cost;
};

TrapezoidEdge trap_edges[MAX_TRAPEZOID_NODES * 8]; // Max edges
int trap_head[MAX_TRAPEZOID_NODES];
int trap_edge_counter;

int trapezoid_start_cols, trapezoid_rows; // M, N from problem
long long trapezoid_values[MAX_TRAPEZOID_DIM][MAX_TRAPEZOID_DIM];

// Map (row, col) to (row, col)_in and (row, col)_out node IDs
inline int get_trap_in_node(int r, int c) { return (r - 1) * (trapezoid_start_cols + trapezoid_rows - 1) + c; }
inline int get_trap_out_node(int r, int c) { return (r - 1) * (trapezoid_start_cols + trapezoid_rows - 1) + c + (trapezoid_rows) * (trapezoid_start_cols + trapezoid_rows - 1); }

int trap_source, trap_sink;

long long trap_min_cost_dist[MAX_TRAPEZOID_NODES];
int trap_path_parent_nodes[MAX_TRAPEZOID_NODES];
int trap_path_edge_indices[MAX_TRAPEZOID_NODES];
bool trap_in_queue[MAX_TRAPEZOID_NODES];

long long total_trap_flow = 0;
long long total_trap_min_cost = 0;

void init_graph() {
    std::memset(trap_head, 0, sizeof(trap_head));
    trap_edge_counter = 1;
}

void add_trap_edge(int u, int v, long long capacity, long long cost) {
    trap_edges[++trap_edge_counter] = {v, trap_head[u], capacity, cost}; trap_head[u] = trap_edge_counter;
    trap_edges[++trap_edge_counter] = {u, trap_head[v], 0, -cost}; trap_head[v] = trap_edge_counter;
}

bool spfa_trap_shortest_path() {
    std::fill(trap_min_cost_dist, trap_min_cost_dist + trap_sink + 1, INF_TRAPEZOID_LL);
    std::fill(trap_in_queue, trap_in_queue + trap_sink + 1, false);
    std::queue<int> q_spfa;

    trap_min_cost_dist[trap_source] = 0;
    q_spfa.push(trap_source);
    trap_in_queue[trap_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        trap_in_queue[u] = false;

        for (int i = trap_head[u]; i; i = trap_edges[i].next_edge_idx) {
            TrapezoidEdge& edge = trap_edges[i];
            if (edge.flow_capacity > 0 && trap_min_cost_dist[edge.target_node] > trap_min_cost_dist[u] + edge.edge_cost) {
                trap_min_cost_dist[edge.target_node] = trap_min_cost_dist[u] + edge.edge_cost;
                trap_path_parent_nodes[edge.target_node] = u;
                trap_path_edge_indices[edge.target_node] = i;

                if (!trap_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    trap_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return trap_min_cost_dist[trap_sink] != INF_TRAPEZOID_LL;
}

void find_min_cost_max_flow_trapezoid() {
    total_trap_flow = 0;
    total_trap_min_cost = 0;
    while (spfa_trap_shortest_path()) {
        long long current_path_flow = INF_TRAPEZOID_LL;

        for (int v = trap_sink; v != trap_source; v = trap_path_parent_nodes[v]) {
            int u = trap_path_parent_nodes[v];
            int edge_idx = trap_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, trap_edges[edge_idx].flow_capacity);
        }

        total_trap_flow += current_path_flow;
        total_trap_min_cost += current_path_flow * trap_min_cost_dist[trap_sink];

        for (int v = trap_sink; v != trap_source; v = trap_path_parent_nodes[v]) {
            int u = trap_path_parent_nodes[v];
            int edge_idx = trap_path_edge_indices[v];
            trap_edges[edge_idx].flow_capacity -= current_path_flow;
            trap_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> trapezoid_start_cols >> trapezoid_rows;

    // Read trapezoid values
    for (int r = 1; r <= trapezoid_rows; ++r) {
        for (int c = 1; c <= trapezoid_start_cols + r - 1; ++c) {
            std::cin >> trapezoid_values[r][c];
        }
    }

    // Determine max_node_id based on total nodes in grid
    int max_node_id_val = 0;
    for (int r = 1; r <= trapezoid_rows; ++r) {
        max_node_id_val = std::max(max_node_id_val, get_trap_out_node(r, trapezoid_start_cols + r - 1));
    }
    trap_source = 0;
    trap_sink = max_node_id_val + 1;

    // Version 1: Each cell and each edge visited at most once
    init_graph();
    for (int r = 1; r <= trapezoid_rows; ++r) {
        for (int c = 1; c <= trapezoid_start_cols + r - 1; ++c) {
            add_trap_edge(get_trap_in_node(r, c), get_trap_out_node(r, c), 1, -trapezoid_values[r][c]); // Cell value once
        }
    }
    for (int r = 1; r < trapezoid_rows; ++r) {
        for (int c = 1; c <= trapezoid_start_cols + r - 1; ++c) {
            add_trap_edge(get_trap_out_node(r, c), get_trap_in_node(r + 1, c), 1, 0); // Move down
            add_trap_edge(get_trap_out_node(r, c), get_trap_in_node(r + 1, c + 1), 1, 0); // Move down-right
        }
    }
    for (int c = 1; c <= trapezoid_start_cols; ++c) {
        add_trap_edge(trap_source, get_trap_in_node(1, c), 1, 0); // Start from first row
    }
    for (int c = 1; c <= trapezoid_start_cols + trapezoid_rows - 1; ++c) {
        add_trap_edge(get_trap_out_node(trapezoid_rows, c), trap_sink, 1, 0); // End at last row
    }
    find_min_cost_max_flow_trapezoid();
    std::cout <> -total_trap_min_cost << std::endl;

    // Version 2: Each cell visited multiple times, each edge once
    init_graph();
    for (int r = 1; r <= trapezoid_rows; ++r) {
        for (int c = 1; c <= trapezoid_start_cols + r - 1; ++c) {
            add_trap_edge(get_trap_in_node(r, c), get_trap_out_node(r, c), INF_TRAPEZOID_LL, -trapezoid_values[r][c]); // Cell value multiple times
        }
    }
    for (int r = 1; r < trapezoid_rows; ++r) {
        for (int c = 1; c <= trapezoid_start_cols + r - 1; ++c) {
            add_trap_edge(get_trap_out_node(r, c), get_trap_in_node(r + 1, c), 1, 0); // Move down, edge once
            add_trap_edge(get_trap_out_node(r, c), get_trap_in_node(r + 1, c + 1), 1, 0); // Move down-right, edge once
        }
    }
    for (int c = 1; c <= trapezoid_start_cols; ++c) {
        add_trap_edge(trap_source, get_trap_in_node(1, c), 1, 0); // Start from first row
    }
    for (int c = 1; c <= trapezoid_start_cols + trapezoid_rows - 1; ++c) {
        add_trap_edge(get_trap_out_node(trapezoid_rows, c), trap_sink, INF_TRAPEZOID_LL, 0); // End at last row
    }
    find_min_cost_max_flow_trapezoid();
    std::cout <> -total_trap_min_cost << std::endl;

    // Version 3: Each cell and each edge visited multiple times
    init_graph();
    for (int r = 1; r <= trapezoid_rows; ++r) {
        for (int c = 1; c <= trapezoid_start_cols + r - 1; ++c) {
            add_trap_edge(get_trap_in_node(r, c), get_trap_out_node(r, c), INF_TRAPEZOID_LL, -trapezoid_values[r][c]); // Cell value multiple times
        }
    }
    for (int r = 1; r < trapezoid_rows; ++r) {
        for (int c = 1; c <= trapezoid_start_cols + r - 1; ++c) {
            add_trap_edge(get_trap_out_node(r, c), get_trap_in_node(r + 1, c), INF_TRAPEZOID_LL, 0); // Move down, edge multiple
            add_trap_edge(get_trap_out_node(r, c), get_trap_in_node(r + 1, c + 1), INF_TRAPEZOID_LL, 0); // Move down-right, edge multiple
        }
    }
    for (int c = 1; c <= trapezoid_start_cols; ++c) {
        add_trap_edge(trap_source, get_trap_in_node(1, c), 1, 0); // Start from first row (still only 1 path from S to each start point)
    }
    for (int c = 1; c <= trapezoid_start_cols + trapezoid_rows - 1; ++c) {
        add_trap_edge(get_trap_out_node(trapezoid_rows, c), trap_sink, INF_TRAPEZOID_LL, 0); // End at last row
    }
    find_min_cost_max_flow_trapezoid();
    std::cout <> -total_trap_min_cost << std::endl;

    return 0;
}

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const int INF_ASSIGNMENT_COST = 1e9 + 7;
const int MAX_ASSIGNMENT_DIM = 55; // Max N dimension
const int MAX_ASSIGNMENT_NODES = MAX_ASSIGNMENT_DIM * 2 + 5; // N persons + N jobs + S + T

struct AssignmentEdge {
    int target_node;
    int next_edge_idx;
    int flow_capacity;
    int edge_cost;
};

AssignmentEdge assign_edges[MAX_ASSIGNMENT_NODES * MAX_ASSIGNMENT_NODES]; // Max N*N edges
int assign_head[MAX_ASSIGNMENT_NODES];
int assign_edge_counter;

int num_assignments; // N
int cost_matrix[MAX_ASSIGNMENT_DIM][MAX_ASSIGNMENT_DIM];

int assign_source, assign_sink;

long long assign_min_cost_dist[MAX_ASSIGNMENT_NODES];
int assign_path_parent_nodes[MAX_ASSIGNMENT_NODES];
int assign_path_edge_indices[MAX_ASSIGNMENT_NODES];
bool assign_in_queue[MAX_ASSIGNMENT_NODES];

long long total_assign_flow = 0;
long long total_assign_min_cost = 0;

void init_assign_graph() {
    std::memset(assign_head, 0, sizeof(assign_head));
    assign_edge_counter = 1;
}

void add_assign_edge(int u, int v, int capacity, int cost) {
    assign_edges[++assign_edge_counter] = {v, assign_head[u], capacity, cost}; assign_head[u] = assign_edge_counter;
    assign_edges[++assign_edge_counter] = {u, assign_head[v], 0, -cost}; assign_head[v] = assign_edge_counter;
}

bool spfa_assign_shortest_path() {
    std::fill(assign_min_cost_dist, assign_min_cost_dist + assign_sink + 1, INF_ASSIGNMENT_COST);
    std::fill(assign_in_queue, assign_in_queue + assign_sink + 1, false);
    std::queue<int> q_spfa;

    assign_min_cost_dist[assign_source] = 0;
    q_spfa.push(assign_source);
    assign_in_queue[assign_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        assign_in_queue[u] = false;

        for (int i = assign_head[u]; i; i = assign_edges[i].next_edge_idx) {
            AssignmentEdge& edge = assign_edges[i];
            if (edge.flow_capacity > 0 && assign_min_cost_dist[edge.target_node] > assign_min_cost_dist[u] + edge.edge_cost) {
                assign_min_cost_dist[edge.target_node] = assign_min_cost_dist[u] + edge.edge_cost;
                assign_path_parent_nodes[edge.target_node] = u;
                assign_path_edge_indices[edge.target_node] = i;

                if (!assign_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    assign_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return assign_min_cost_dist[assign_sink] != INF_ASSIGNMENT_COST;
}

void find_min_cost_max_flow_assign() {
    total_assign_flow = 0;
    total_assign_min_cost = 0;
    while (spfa_assign_shortest_path()) {
        long long current_path_flow = INF_ASSIGNMENT_COST; // Max flow on path is 1 here

        for (int v = assign_sink; v != assign_source; v = assign_path_parent_nodes[v]) {
            int u = assign_path_parent_nodes[v];
            int edge_idx = assign_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, (long long)assign_edges[edge_idx].flow_capacity);
        }

        total_assign_flow += current_path_flow;
        total_assign_min_cost += current_path_flow * assign_min_cost_dist[assign_sink];

        for (int v = assign_sink; v != assign_source; v = assign_path_parent_nodes[v]) {
            int u = assign_path_parent_nodes[v];
            int edge_idx = assign_path_edge_indices[v];
            assign_edges[edge_idx].flow_capacity -= current_path_flow;
            assign_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_assignments;

    for (int i = 1; i <= num_assignments; ++i) {
        for (int j = 1; j <= num_assignments; ++j) {
            std::cin >> cost_matrix[i][j];
        }
    }

    assign_source = 0;
    assign_sink = 2 * num_assignments + 1; // Persons 1 to N, Jobs N+1 to 2N

    // --- Minimum Cost Assignment ---
    init_assign_graph();
    for (int i = 1; i <= num_assignments; ++i) { // Persons
        for (int j = 1; j <= num_assignments; ++j) { // Jobs
            add_assign_edge(i, num_assignments + j, 1, cost_matrix[i][j]);
        }
    }
    for (int i = 1; i <= num_assignments; ++i) add_assign_edge(assign_source, i, 1, 0); // S to Persons
    for (int i = 1; i <= num_assignments; ++i) add_assign_edge(num_assignments + i, assign_sink, 1, 0); // Jobs to T
    
    find_min_cost_max_flow_assign();
    std::cout <> total_assign_min_cost << std::endl;

    // --- Maximum Benefit Assignment ---
    init_assign_graph();
    for (int i = 1; i <= num_assignments; ++i) { // Persons
        for (int j = 1; j <= num_assignments; ++j) { // Jobs
            add_assign_edge(i, num_assignments + j, 1, -cost_matrix[i][j]); // Negative cost for max benefit
        }
    }
    for (int i = 1; i <= num_assignments; ++i) add_assign_edge(assign_source, i, 1, 0); // S to Persons
    for (int i = 1; i <= num_assignments; ++i) add_assign_edge(num_assignments + i, assign_sink, 1, 0); // Jobs to T

    find_min_cost_max_flow_assign();
    std::cout <> -total_assign_min_cost << std::endl; // Output positive benefit

    return 0;
}

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const long long INF_TRANSPORT_LL = std::numeric_limits<long long>::max() / 2;
const int MAX_TRANSPORT_DIM = 105; // Max N factories, M warehouses
const int MAX_TRANSPORT_NODES = MAX_TRANSPORT_DIM * 2 + 5; // N factories + M warehouses + S + T

struct TransportEdge {
    int target_node;
    int next_edge_idx;
    long long flow_capacity;
    long long edge_cost;
};

TransportEdge transport_edges[MAX_TRANSPORT_NODES * MAX_TRANSPORT_NODES]; // Max N*M edges
int transport_head[MAX_TRANSPORT_NODES];
int transport_edge_counter;

int num_factories, num_warehouses;
int factory_supplies[MAX_TRANSPORT_DIM];
int warehouse_demands[MAX_TRANSPORT_DIM];
int transport_costs[MAX_TRANSPORT_DIM][MAX_TRANSPORT_DIM];

int transport_source, transport_sink;

long long transport_min_cost_dist[MAX_TRANSPORT_NODES];
int transport_path_parent_nodes[MAX_TRANSPORT_NODES];
int transport_path_edge_indices[MAX_TRANSPORT_NODES];
bool transport_in_queue[MAX_TRANSPORT_NODES];

long long total_transport_flow = 0;
long long total_transport_min_cost = 0;

void init_transport_graph() {
    std::memset(transport_head, 0, sizeof(transport_head));
    transport_edge_counter = 1;
}

void add_transport_edge(int u, int v, long long capacity, long long cost) {
    transport_edges[++transport_edge_counter] = {v, transport_head[u], capacity, cost}; transport_head[u] = transport_edge_counter;
    transport_edges[++transport_edge_counter] = {u, transport_head[v], 0, -cost}; transport_head[v] = transport_edge_counter;
}

bool spfa_transport_shortest_path() {
    std::fill(transport_min_cost_dist, transport_min_cost_dist + transport_sink + 1, INF_TRANSPORT_LL);
    std::fill(transport_in_queue, transport_in_queue + transport_sink + 1, false);
    std::queue<int> q_spfa;

    transport_min_cost_dist[transport_source] = 0;
    q_spfa.push(transport_source);
    transport_in_queue[transport_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        transport_in_queue[u] = false;

        for (int i = transport_head[u]; i; i = transport_edges[i].next_edge_idx) {
            TransportEdge& edge = transport_edges[i];
            if (edge.flow_capacity > 0 && transport_min_cost_dist[edge.target_node] > transport_min_cost_dist[u] + edge.edge_cost) {
                transport_min_cost_dist[edge.target_node] = transport_min_cost_dist[u] + edge.edge_cost;
                transport_path_parent_nodes[edge.target_node] = u;
                transport_path_edge_indices[edge.target_node] = i;

                if (!transport_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    transport_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return transport_min_cost_dist[transport_sink] != INF_TRANSPORT_LL;
}

void find_min_cost_max_flow_transport() {
    total_transport_flow = 0;
    total_transport_min_cost = 0;
    while (spfa_transport_shortest_path()) {
        long long current_path_flow = INF_TRANSPORT_LL;

        for (int v = transport_sink; v != transport_source; v = transport_path_parent_nodes[v]) {
            int u = transport_path_parent_nodes[v];
            int edge_idx = transport_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, transport_edges[edge_idx].flow_capacity);
        }

        total_transport_flow += current_path_flow;
        total_transport_min_cost += current_path_flow * transport_min_cost_dist[transport_sink];

        for (int v = transport_sink; v != transport_source; v = transport_path_parent_nodes[v]) {
            int u = transport_path_parent_nodes[v];
            int edge_idx = transport_path_edge_indices[v];
            transport_edges[edge_idx].flow_capacity -= current_path_flow;
            transport_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_factories >> num_warehouses;
    
    transport_source = 0;
    transport_sink = num_factories + num_warehouses + 1; // Factories 1 to N, Warehouses N+1 to N+M

    for (int i = 1; i <= num_factories; ++i) std::cin >> factory_supplies[i];
    for (int i = 1; i <= num_warehouses; ++i) std::cin >> warehouse_demands[i];
    for (int i = 1; i <= num_factories; ++i) {
        for (int j = 1; j <= num_warehouses; ++j) {
            std::cin >> transport_costs[i][j];
        }
    }

    // --- Minimum Cost Transportation ---
    init_transport_graph();
    for (int i = 1; i <= num_factories; ++i) add_transport_edge(transport_source, i, factory_supplies[i], 0); // S to Factories
    for (int i = 1; i <= num_warehouses; ++i) add_transport_edge(num_factories + i, transport_sink, warehouse_demands[i], 0); // Warehouses to T
    for (int i = 1; i <= num_factories; ++i) {
        for (int j = 1; j <= num_warehouses; ++j) {
            add_transport_edge(i, num_factories + j, INF_TRANSPORT_LL, transport_costs[i][j]); // Factories to Warehouses
        }
    }
    find_min_cost_max_flow_transport();
    std::cout <> total_transport_min_cost << std::endl;

    // --- Maximum Benefit Transportation ---
    init_transport_graph();
    for (int i = 1; i <= num_factories; ++i) add_transport_edge(transport_source, i, factory_supplies[i], 0);
    for (int i = 1; i <= num_warehouses; ++i) add_transport_edge(num_factories + i, transport_sink, warehouse_demands[i], 0);
    for (int i = 1; i <= num_factories; ++i) {
        for (int j = 1; j <= num_warehouses; ++j) {
            add_transport_edge(i, num_factories + j, INF_TRANSPORT_LL, -transport_costs[i][j]); // Negative cost for max benefit
        }
    }
    find_min_cost_max_flow_transport();
    std::cout <> -total_transport_min_cost << std::endl; // Output positive benefit

    return 0;
}

#include <iostream>
#include <vector>
#lt;queue>
#lt;cstring> // For memset
#lt;algorithm>
#lt;limits>

const long long INF_LOAD_LL = std::numeric_limits<long long>::max() / 2;
const int MAX_LOAD_NODES = 205; // Max N nodes + S + T

struct LoadEdge {
    int target_node;
    int next_edge_idx;
    long long flow_capacity;
    long long edge_cost;
};

LoadEdge load_edges[MAX_LOAD_NODES * 4]; // Each node has up to 4 edges (S, T, i-1, i+1)
int load_head[MAX_LOAD_NODES];
int load_edge_counter = 1;

int num_servers; // N
long long server_resources[MAX_LOAD_NODES];
long long average_resource_per_server;

int load_source, load_sink;

long long load_min_cost_dist[MAX_LOAD_NODES];
int load_path_parent_nodes[MAX_LOAD_NODES];
int load_path_edge_indices[MAX_LOAD_NODES];
bool load_in_queue[MAX_LOAD_NODES];

long long total_load_flow = 0;
long long total_load_min_cost = 0;

void add_load_edge(int u, int v, long long capacity, long long cost) {
    load_edges[++load_edge_counter] = {v, load_head[u], capacity, cost}; load_head[u] = load_edge_counter;
    load_edges[++load_edge_counter] = {u, load_head[v], 0, -cost}; load_head[v] = load_edge_counter;
}

bool spfa_load_shortest_path() {
    std::fill(load_min_cost_dist, load_min_cost_dist + load_sink + 1, INF_LOAD_LL);
    std::fill(load_in_queue, load_in_queue + load_sink + 1, false);
    std::queue<int> q_spfa;

    load_min_cost_dist[load_source] = 0;
    q_spfa.push(load_source);
    load_in_queue[load_source] = true;

    while (!q_spfa.empty()) {
        int u = q_spfa.front();
        q_spfa.pop();
        load_in_queue[u] = false;

        for (int i = load_head[u]; i; i = load_edges[i].next_edge_idx) {
            LoadEdge& edge = load_edges[i];
            if (edge.flow_capacity > 0 && load_min_cost_dist[edge.target_node] > load_min_cost_dist[u] + edge.edge_cost) {
                load_min_cost_dist[edge.target_node] = load_min_cost_dist[u] + edge.edge_cost;
                load_path_parent_nodes[edge.target_node] = u;
                load_path_edge_indices[edge.target_node] = i;

                if (!load_in_queue[edge.target_node]) {
                    q_spfa.push(edge.target_node);
                    load_in_queue[edge.target_node] = true;
                }
            }
        }
    }
    return load_min_cost_dist[load_sink] != INF_LOAD_LL;
}

void find_min_cost_max_flow_load() {
    total_load_flow = 0;
    total_load_min_cost = 0;
    while (spfa_load_shortest_path()) {
        long long current_path_flow = INF_LOAD_LL;

        for (int v = load_sink; v != load_source; v = load_path_parent_nodes[v]) {
            int u = load_path_parent_nodes[v];
            int edge_idx = load_path_edge_indices[v];
            current_path_flow = std::min(current_path_flow, load_edges[edge_idx].flow_capacity);
        }

        total_load_flow += current_path_flow;
        total_load_min_cost += current_path_flow * load_min_cost_dist[load_sink];

        for (int v = load_sink; v != load_source; v = load_path_parent_nodes[v]) {
            int u = load_path_parent_nodes[v];
            int edge_idx = load_path_edge_indices[v];
            load_edges[edge_idx].flow_capacity -= current_path_flow;
            load_edges[edge_idx ^ 1].flow_capacity += current_path_flow;
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    std::cin >> num_servers;
    long long total_resources = 0;
    for (int i = 1; i <= num_servers; ++i) {
        std::cin >> server_resources[i];
        total_resources += server_resources[i];
    }

    average_resource_per_server = total_resources / num_servers;

    load_source = 0;
    load_sink = num_servers + 1;

    for (int i = 1; i <= num_servers; ++i) {
        if (server_resources[i] > average_resource_per_server) {
            add_load_edge(load_source, i, server_resources[i] - average_resource_per_server, 0);
        } else if (server_resources[i] < average_resource_per_server) {
            add_load_edge(i, load_sink, average_resource_per_server - server_resources[i], 0);
        }
    }

    // Connect adjacent servers for resource transfer (circularly)
    for (int i = 1; i <= num_servers; ++i) {
        int next_server = (i % num_servers) + 1; // Circular connection
        add_load_edge(i, next_server, INF_LOAD_LL, 1); // Cost 1 for transfer
        add_load_edge(next_server, i, INF_LOAD_LL, 1); // Bidirectional
    }

    find_min_cost_max_flow_load();

    std::cout <> total_load_min_cost << std::endl;

    return 0;
}