結果
| 問題 |
No.2328 Build Walls
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:35 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 12,218 bytes |
| コンパイル時間 | 1,422 ms |
| コンパイル使用メモリ | 100,216 KB |
| 実行使用メモリ | 89,900 KB |
| 最終ジャッジ日時 | 2025-05-14 13:16:46 |
| 合計ジャッジ時間 | 6,497 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 11 TLE * 1 -- * 22 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <utility> // For std::pair
// Use long long for capacities and flow values to avoid overflow.
using ll = long long;
// Define a large constant to represent infinity.
// It should be larger than the maximum possible finite cut capacity.
// The maximum capacity could be sum of all A_ij, roughly (H-2)*W*800.
// For H, W <= 800, this is about 798 * 800 * 800 ~= 5.1 * 10^8.
// Using 10^15 is sufficiently large.
const ll INF = 1e15;
// Structure to represent an edge in the flow network graph.
struct Edge {
int to; // Destination node index
ll cap; // Current capacity of the edge
int rev; // Index of the reverse edge in the adjacency list of 'to' node
};
// Global variables for the graph and flow algorithm state.
std::vector<std::vector<Edge>> graph; // Adjacency list representation of the graph.
std::vector<int> level; // Stores level of each node in BFS (for Dinic).
std::vector<int> iter; // Stores iterator/index for DFS search to optimize (for Dinic).
// Function to add a directed edge and its corresponding reverse edge to the graph.
// This is standard practice for max flow algorithms.
void add_edge(int from, int to, ll cap) {
// Add the forward edge
graph[from].push_back({to, cap, (int)graph[to].size()});
// Add the reverse edge with initial capacity 0.
// The capacity of the reverse edge increases when flow is pushed back.
graph[to].push_back({from, 0, (int)graph[from].size() - 1});
}
// Breadth-First Search to compute the level graph for Dinic's algorithm.
// Returns true if the sink 't' is reachable from the source 's'.
bool bfs(int s, int t) {
level.assign(graph.size(), -1); // Initialize all levels to -1 (unvisited).
std::queue<int> q;
level[s] = 0; // Level of source node is 0.
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
// Explore neighbors of node v
for (const auto& edge : graph[v]) {
// If edge has positive capacity and the destination node hasn't been visited yet
if (edge.cap > 0 && level[edge.to] < 0) {
level[edge.to] = level[v] + 1; // Set level of neighbor node.
q.push(edge.to); // Add neighbor node to the queue.
}
}
}
// Return true if the sink node 't' was reached (level is not -1).
return level[t] != -1;
}
// Depth-First Search to find an augmenting path in the level graph and push flow.
// Returns the amount of flow pushed along the path found.
ll dfs(int v, int t, ll f) {
// Base case: If we reached the sink node 't', return the available flow 'f'.
if (v == t) return f;
// Use the iterator 'iter[v]' to optimize DFS. This prevents re-exploring edges
// that have already been determined to not lead to an augmenting path in this phase.
for (int& i = iter[v]; i < graph[v].size(); ++i) {
Edge& e = graph[v][i]; // Reference to the current edge.
// Check if edge has capacity and leads to a node in the next level.
if (e.cap > 0 && level[v] < level[e.to]) {
// Recursively call DFS for the neighbor node. Push minimum of remaining flow 'f' and edge capacity 'e.cap'.
ll d = dfs(e.to, t, std::min(f, e.cap));
if (d > 0) { // If flow 'd' was successfully pushed down this path
e.cap -= d; // Decrease capacity of the forward edge.
graph[e.to][e.rev].cap += d; // Increase capacity of the reverse edge.
return d; // Return the amount of flow pushed.
}
}
}
// If no augmenting path is found from node 'v', return 0.
return 0;
}
// Computes the maximum flow from source 's' to sink 't' using Dinic's algorithm.
ll max_flow(int s, int t) {
ll total_flow = 0;
// Keep finding augmenting paths as long as the sink is reachable from the source in the residual graph.
while (bfs(s, t)) { // Compute level graph using BFS.
iter.assign(graph.size(), 0); // Reset DFS iterators for the new level graph.
ll flow_increment;
// Use DFS to find and push flow along augmenting paths in the current level graph.
while ((flow_increment = dfs(s, t, INF)) > 0) {
total_flow += flow_increment; // Add the pushed flow to the total flow.
}
}
// According to Max-Flow Min-Cut theorem, max flow equals min cut capacity.
// Check if the calculated flow is effectively infinite. This suggests an issue, possibly an unblockable path
// that was not caught by the initial BFS check, or total costs sum up to INF (unlikely).
if (total_flow >= INF) return -1;
return total_flow; // Return the total maximum flow.
}
int main() {
// Use fast I/O operations.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int H, W; // Read grid dimensions Height and Width.
std::cin >> H >> W;
// Read the cost matrix A. Use 1-based indexing for rows and columns as in problem statement.
// A[i][j] stores the cost to build a wall at cell (i, j).
// Valid indices for costs are i=2..H-1, j=1..W.
std::vector<std::vector<ll>> A(H + 1, std::vector<ll>(W + 1));
for (int i = 2; i <= H - 1; ++i) {
for (int j = 1; j <= W; ++j) {
std::cin >> A[i][j];
}
}
// --- Initial Check Phase ---
// Perform BFS on the grid to check if there exists an "unblockable" path from row 1 to row H.
// An unblockable path consists ONLY of cells that cannot have walls built on them.
// These are cells in row 1, row H, or cells (i, j) where 2 <= i <= H-1 and A[i][j] == -1.
std::queue<std::pair<int, int>> q_check; // Queue for BFS. Stores cell coordinates (row, col).
std::vector<std::vector<bool>> visited(H + 1, std::vector<bool>(W + 1, false)); // Keep track of visited cells.
// Initialize BFS queue with all cells in row 1. These are the starting points.
for (int j = 1; j <= W; ++j) {
if (!visited[1][j]) {
q_check.push({1, j});
visited[1][j] = true;
}
}
bool possible_to_reach_H = false; // Flag to indicate if an unblockable path reaches row H.
int dr[] = {-1, 1, 0, 0}; // Delta row for adjacent cells: up, down, left, right.
int dc[] = {0, 0, -1, 1}; // Delta column for adjacent cells.
// Run the BFS check.
while (!q_check.empty()) {
std::pair<int, int> curr = q_check.front();
q_check.pop();
int r = curr.first;
int c = curr.second;
// If BFS reaches any cell in row H, an unblockable path exists.
if (r == H) {
possible_to_reach_H = true;
break; // Exit BFS early.
}
// Explore neighbors of the current cell.
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k]; // Neighbor row.
int nc = c + dc[k]; // Neighbor column.
// Check if neighbor is within grid bounds and not visited yet.
if (nr >= 1 && nr <= H && nc >= 1 && nc <= W && !visited[nr][nc]) {
bool passable = false; // Check if the neighbor cell is inherently unblockable.
if (nr == 1 || nr == H) { // Cells in row 1 and H are always passable (start/end zones, no walls).
passable = true;
} else { // For cells in intermediate rows (2 to H-1).
// Check if wall cannot be built (A[nr][nc] == -1).
if (A[nr][nc] == -1) {
passable = true;
}
}
// If the neighbor cell is passable according to the check.
if (passable) {
visited[nr][nc] = true; // Mark as visited.
q_check.push({nr, nc}); // Add to queue for further exploration.
}
}
}
}
// If the BFS check found an unblockable path to row H, output -1 and terminate.
if (possible_to_reach_H) {
std::cout << -1 << std::endl;
return 0;
}
// --- Max Flow Phase ---
// If no unblockable path exists, proceed to calculate the minimum cost to block all paths using max flow.
int N_cells = H * W; // Total number of cells in the grid.
int source = 2 * N_cells; // Index for the source node S.
int sink = 2 * N_cells + 1; // Index for the sink node T.
graph.resize(2 * N_cells + 2); // Resize the graph adjacency list structure.
// Lambda functions to map cell coordinates (r, c) to node indices in the graph.
// Each cell (r,c) is split into an in-node and an out-node.
auto node_in = [&](int r, int c) {
// Calculate index for the in-node of cell (r, c).
return 2 * ((r - 1) * W + (c - 1));
};
auto node_out = [&](int r, int c) {
// Calculate index for the out-node of cell (r, c).
return 2 * ((r - 1) * W + (c - 1)) + 1;
};
// Build the flow network graph based on the grid.
for (int i = 1; i <= H; ++i) { // Iterate through rows.
for (int j = 1; j <= W; ++j) { // Iterate through columns.
int u_in = node_in(i, j); // Get index of in-node for cell (i, j).
int v_out = node_out(i, j); // Get index of out-node for cell (i, j).
// Add the edge connecting the in-node to the out-node for cell (i, j).
// The capacity of this edge represents the cost to build a wall at (i, j),
// or infinity if a wall cannot be built.
ll cost;
if (i == 1 || i == H) { // Walls cannot be built in row 1 or H.
cost = INF;
} else { // For intermediate rows 2 to H-1.
cost = A[i][j]; // Cost is given by A[i][j].
if (cost == -1) { // If A[i][j] is -1, wall cannot be built.
cost = INF; // Represent impossibility with infinite capacity.
}
}
add_edge(u_in, v_out, cost); // Add the edge with calculated capacity.
// Add edges representing possible movement between adjacent cells.
// These edges have infinite capacity as movement itself is free.
// Consider only right and down neighbors to add connections for each pair exactly once.
// Check right neighbor (i, j+1)
if (j + 1 <= W) {
int neighbor_in = node_in(i, j + 1);
int neighbor_out = node_out(i, j + 1);
// Add edge from (i, j)_out to (i, j+1)_in (movement right).
add_edge(v_out, neighbor_in, INF);
// Add edge from (i, j+1)_out to (i, j)_in (movement left).
add_edge(neighbor_out, u_in, INF);
}
// Check down neighbor (i+1, j)
if (i + 1 <= H) {
int neighbor_in = node_in(i + 1, j);
int neighbor_out = node_out(i + 1, j);
// Add edge from (i, j)_out to (i+1, j)_in (movement down).
add_edge(v_out, neighbor_in, INF);
// Add edge from (i+1, j)_out to (i, j)_in (movement up).
add_edge(neighbor_out, u_in, INF);
}
}
}
// Connect the global source node S to all in-nodes of cells in row 1.
// These represent the possible starting points for Sepa-kun. Infinite capacity edges.
for (int j = 1; j <= W; ++j) {
add_edge(source, node_in(1, j), INF);
}
// Connect all out-nodes of cells in row H to the global sink node T.
// These represent the target destination cells for Sepa-kun. Infinite capacity edges.
for (int j = 1; j <= W; ++j) {
add_edge(node_out(H, j), sink, INF);
}
// Calculate the maximum flow from source to sink using Dinic's algorithm.
// By the Max-Flow Min-Cut theorem, this value equals the minimum cut capacity.
ll min_cost = max_flow(source, sink);
// Output the minimum cost. If min_cost is -1 (returned by max_flow function), it means impossible.
std::cout << min_cost << std::endl;
return 0;
}