結果
| 問題 |
No.957 植林
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:19 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,518 bytes |
| コンパイル時間 | 1,204 ms |
| コンパイル使用メモリ | 89,948 KB |
| 実行使用メモリ | 28,980 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:30 |
| 合計ジャッジ時間 | 7,026 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 15 TLE * 1 -- * 29 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <numeric>
using namespace std;
// Use long long for capacities and flow values due to potentially large costs and gains (up to 10^9)
typedef long long ll;
// Define a large constant for infinite capacity edges.
// The maximum possible sum of finite capacities is roughly (H+W+HW) * 10^9.
// With H, W <= 300, this is about (300 + 300 + 300*300) * 10^9 = 90600 * 10^9 < 10^14.
// So 10^15 is a safe value for infinity.
const ll INF = 1e15;
// Structure to represent an edge in the flow network graph
struct Edge {
int to; // The destination node index of the edge
ll capacity; // The current capacity of the edge
int rev; // The index of the reverse edge in the adjacency list of the 'to' node
// This is used to efficiently update residual capacities.
};
vector<vector<Edge>> graph; // Adjacency list representation of the graph
vector<int> level; // Stores the level (distance from source) of each node in the BFS phase of Dinic's algorithm
vector<int> iter; // Stores the current edge index being explored from each node in the DFS phase of Dinic's algorithm
// This helps avoid re-exploring edges that are already saturated or lead to dead ends in the current level graph.
// Function to add a directed edge and its corresponding reverse edge to the graph
// In the context of max flow, reverse edges are needed for the residual graph concept.
void add_edge(int u, int v, ll cap) {
// Add the forward edge u -> v with the given capacity
graph[u].push_back({v, cap, (int)graph[v].size()});
// Add the reverse edge v -> u with initial capacity 0
// This capacity will increase if flow is pushed back along the original edge u -> v
graph[v].push_back({u, 0, (int)graph[u].size() - 1});
}
// Breadth-First Search (BFS) to build the level graph required by Dinic's algorithm
// It computes the shortest path distance (in terms of number of edges) from the source 's' to all reachable nodes.
bool bfs(int s, int t) {
level.assign(graph.size(), -1); // Initialize all levels to -1 (unvisited)
queue<int> q;
level[s] = 0; // Level of the 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 the edge has remaining capacity and the destination node hasn't been visited yet
if (edge.capacity > 0 && level[edge.to] < 0) {
level[edge.to] = level[v] + 1; // Assign level to the neighbor
q.push(edge.to);
}
}
}
// Returns true if the sink 't' is reachable from the source 's', false otherwise
// If sink is unreachable, no more augmenting paths can be found.
return level[t] != -1;
}
// Depth-First Search (DFS) to find an augmenting path in the level graph and push flow along it
// It attempts to push 'f' units of flow from node 'v' to the sink 't'.
ll dfs(int v, int t, ll f) {
// Base case: If we have reached the sink node, return the amount of flow 'f' that reached it.
if (v == t) return f;
// Iterate through the edges starting from the index stored in 'iter[v]'
// This optimization prevents re-checking edges that have already been fully explored in the current DFS phase.
for (int& i = iter[v]; i < graph[v].size(); ++i) {
Edge& e = graph[v][i]; // Get a reference to the current edge
// Check if the edge has remaining capacity and leads to a node in the next level of the level graph
if (e.capacity > 0 && level[v] < level[e.to]) {
// Recursively call DFS for the next node 'e.to'
// The amount of flow to push is limited by the minimum of the remaining flow 'f' and the edge's capacity 'e.capacity'.
ll d = dfs(e.to, t, min(f, e.capacity));
// If flow 'd' was successfully pushed to the sink through this path (d > 0)
if (d > 0) {
e.capacity -= d; // Decrease the capacity of the forward edge
graph[e.to][e.rev].capacity += d; // Increase the capacity of the reverse edge (in the residual graph)
return d; // Return the amount of flow pushed
}
}
}
// If no augmenting path could be found from node 'v'
return 0;
}
// Dinic's algorithm implementation to compute the maximum flow from source 's' to sink 't'
ll max_flow(int s, int t) {
ll total_flow = 0; // Initialize total flow to 0
// Repeat the process as long as BFS finds that the sink is reachable from the source (i.e., an augmenting path might exist)
while (bfs(s, t)) {
iter.assign(graph.size(), 0); // Reset the iterators for the DFS phase
ll flow_increment;
// Keep performing DFS to find augmenting paths and push flow along them until no more flow can be pushed 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
}
}
return total_flow; // Return the computed maximum flow
}
int main() {
// Faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int H, W; // Read grid dimensions: Height H, Width W
cin >> H >> W;
// Read the costs G[i][j] for planting a tree at cell (i, j)
vector<vector<ll>> G(H, vector<ll>(W));
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
cin >> G[i][j];
}
}
// Read the row bonuses R[i]
vector<ll> R(H);
ll total_potential_gain = 0; // Initialize the total potential gain (sum of all bonuses)
for (int i = 0; i < H; ++i) {
cin >> R[i];
total_potential_gain += R[i];
}
// Read the column bonuses C[j] and add them to the total potential gain
vector<ll> C(W);
for (int j = 0; j < W; ++j) {
cin >> C[j];
total_potential_gain += C[j];
}
// Calculate the total number of nodes required for the graph construction
// Nodes: Source, Sink, H*W cell nodes, H row nodes, W column nodes
int N_nodes = 2 + H * W + H + W;
int S = 0; // Source node index is conventionally 0
int T = N_nodes - 1; // Sink node index is the last index
graph.resize(N_nodes); // Resize the adjacency list vector to accommodate all nodes
// Helper lambda functions to map grid coordinates (0-based) and row/column indices to graph node indices
// Cell (r, c) -> node index 1 + r*W + c (range [1, H*W])
auto P_idx = [&](int r, int c) { return 1 + r * W + c; };
// Row r -> node index 1 + H*W + r (range [1+H*W, H*W+H])
auto ROW_idx = [&](int r) { return 1 + H * W + r; };
// Column c -> node index 1 + H*W + H + c (range [1+H*W+H, H*W+H+W])
auto COL_idx = [&](int c) { return 1 + H * W + H + c; };
// Construct the graph edges according to the min-cut formulation:
// 1. Edges from Source S to ROW_i nodes with capacity R[i]
for (int i = 0; i < H; ++i) {
add_edge(S, ROW_idx(i), R[i]);
}
// 2. Edges from Source S to COL_j nodes with capacity C[j]
for (int j = 0; j < W; ++j) {
add_edge(S, COL_idx(j), C[j]);
}
// 3. Edges from P_{i,j} nodes to Sink T with capacity G[i][j]
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
add_edge(P_idx(i, j), T, G[i][j]);
}
}
// 4. Infinite capacity edges from ROW_i nodes to corresponding P_{i,j} nodes (dependency constraint)
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
add_edge(ROW_idx(i), P_idx(i, j), INF);
}
}
// 5. Infinite capacity edges from COL_j nodes to corresponding P_{i,j} nodes (dependency constraint)
for (int j = 0; j < W; ++j) {
for (int i = 0; i < H; ++i) {
add_edge(COL_idx(j), P_idx(i, j), INF);
}
}
// Calculate the minimum cut capacity using the max-flow min-cut theorem.
// The max flow value equals the min cut capacity.
ll min_cut_cost = max_flow(S, T);
// The maximum profit is derived from the min-cut formulation:
// Max Profit = Total Potential Gain - Minimum Loss (Min Cut Cost)
ll max_profit = total_potential_gain - min_cut_cost;
// Output the calculated maximum profit
cout << max_profit << endl;
return 0;
}