結果
| 問題 |
No.1324 Approximate the Matrix
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:19:39 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 167 ms / 2,000 ms |
| コード長 | 11,532 bytes |
| コンパイル時間 | 1,389 ms |
| コンパイル使用メモリ | 99,796 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:20:51 |
| 合計ジャッジ時間 | 4,702 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 42 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <queue>
#include <limits>
using namespace std;
// Define long long for larger integer types
typedef long long ll;
// Define a large constant for infinity, carefully chosen to avoid overflow during additions
const ll INF = numeric_limits<ll>::max() / 3;
// Structure to represent edges in the graph
struct Edge {
int to; // Target node index
int rev; // Index of the reverse edge in the adjacency list of the target node G[to]
ll cap; // Original capacity of the edge
ll flow; // Current flow on the edge
int P; // P_ij value associated with the edge (for convex cost calculation), -1 if not applicable
bool is_convex; // Flag indicating if the edge has a convex cost function (P_ij - x)^2
};
vector<vector<Edge>> G; // Adjacency list representation of the graph
vector<ll> h; // Potentials for nodes (used in Dijkstra with potentials)
vector<ll> dist; // Distances from the source node in Dijkstra's algorithm
vector<int> prev_v; // Stores the previous vertex in the shortest path found by Dijkstra
vector<int> prev_e; // Stores the index of the edge used to reach the current vertex from prev_v
vector<bool> prev_fwd; // Stores whether the edge used was in the forward direction
int N_nodes; // Total number of nodes in the graph
// Function to add an edge and its corresponding reverse edge to the graph
// u, v: source and target nodes
// cap: capacity of the edge
// P_val: parameter P_ij for convex cost calculation. If -1, edge has 0 cost.
void add_edge(int u, int v, ll cap, int P_val = -1) {
bool convex = (P_val != -1); // Determine if the edge has convex cost
// Add the forward edge u -> v
G[u].push_back({v, (int)G[v].size(), cap, 0, P_val, convex});
// Add the reverse edge v -> u. Initial capacity is 0. P_val is copied for consistency.
G[v].push_back({u, (int)G[u].size() - 1, 0, 0, P_val, convex});
}
// Function to compute the minimum cost flow using the successive shortest path algorithm (Primal-Dual)
// adapted for convex quadratic costs of the form (P_ij - x)^2.
// s: source node index
// t: sink node index
// K: total required flow
// Returns the sum of marginal costs accumulated, which equals Sum(c(Q_ij) - c(0))
ll min_cost_flow(int s, int t, ll K) {
ll total_algo_cost = 0; // Accumulates the sum of marginal costs for the flow pushed
h.assign(N_nodes, 0); // Initialize potentials to 0 for all nodes
ll current_total_flow = 0; // Tracks the total flow pushed so far
prev_fwd.resize(N_nodes); // Resize the path reconstruction helper vector
// Loop until the required total flow K is reached
while (current_total_flow < K) {
dist.assign(N_nodes, INF); // Initialize distances to infinity
dist[s] = 0; // Distance from source to itself is 0
prev_v.assign(N_nodes, -1); // Reset path reconstruction info
prev_e.assign(N_nodes, -1);
// Use a min-priority queue for Dijkstra's algorithm
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, s}); // Push the source node with distance 0
// Dijkstra's algorithm main loop
while (!pq.empty()) {
ll d = pq.top().first; // Current shortest distance found
int u = pq.top().second; // Node with the current shortest distance
pq.pop();
// If we found a shorter path to u already, skip this element
if (d > dist[u]) continue;
// Explore edges starting from node u
for (int i = 0; i < G[u].size(); ++i) {
Edge &e = G[u][i]; // Current edge u -> v
int v = e.to;
// Try relaxing using the forward edge u -> v in the residual graph
if (e.cap - e.flow > 0) { // Check if there is residual capacity
ll marginal_cost;
// Calculate the marginal cost for pushing 1 unit of flow
if (e.is_convex) {
// Marginal cost for convex quadratic cost (P-x)^2 is 1 - 2P + 2x
marginal_cost = 1 - 2LL * e.P + 2LL * e.flow;
} else {
// For edges with 0 cost function (e.g., source/sink connections), marginal cost is 0
marginal_cost = 0;
}
// Calculate the reduced cost using potentials: cost' = cost + h[u] - h[v]
ll reduced_cost = marginal_cost + h[u] - h[v];
// If a shorter path to v is found via u using this edge forward
if (dist[u] != INF && dist[u] + reduced_cost < dist[v]) {
dist[v] = dist[u] + reduced_cost; // Update distance
prev_v[v] = u; // Record predecessor vertex
prev_e[v] = i; // Record index of edge e in G[u]
prev_fwd[v] = true; // Mark that this edge was used in the forward direction
pq.push({dist[v], v}); // Push updated distance to priority queue
}
}
// Try relaxing using the backward edge u <- v in the residual graph
// This corresponds to reducing flow on the original edge v -> u
Edge &rev_e = G[v][e.rev]; // Get the original edge v -> u
if (rev_e.flow > 0) { // Check if there is flow on v -> u that can be pushed back
ll marginal_cost_backward;
// Calculate the cost of the backward edge u -> v in the residual graph
if (rev_e.is_convex) {
// Cost of pushing back flow x on edge (v -> u) with parameter P is 2P - 2x + 1
marginal_cost_backward = 1 + 2LL * rev_e.P - 2LL * rev_e.flow;
} else {
marginal_cost_backward = 0; // Cost is 0 for non-convex edges
}
// Calculate reduced cost for the backward edge u -> v
ll reduced_cost_backward = marginal_cost_backward + h[u] - h[v];
// If a shorter path to v is found via u using this edge backward
if (dist[u] != INF && dist[u] + reduced_cost_backward < dist[v]) {
dist[v] = dist[u] + reduced_cost_backward; // Update distance
prev_v[v] = u; // Record predecessor vertex
prev_e[v] = i; // Store index of edge e=(u,v). Path reconstruction uses this to find the reverse edge.
prev_fwd[v] = false; // Mark that this edge was used in the backward direction
pq.push({dist[v], v}); // Push updated distance
}
}
}
}
// If the sink t is unreachable, it means we cannot push more flow. Break the loop.
// Based on problem statement G is non-empty, this should only happen if K=0 or if K is achieved.
if (dist[t] == INF) {
break;
}
// Update potentials h[v] for all nodes using the shortest path distances found by Dijkstra
// h[v] = h[v] + dist[v]. This ensures reduced costs remain non-negative.
for (int i = 0; i < N_nodes; ++i) {
if (dist[i] != INF) { // Only update potential if node is reachable
h[i] += dist[i];
}
}
// Augment flow by 1 unit along the found shortest path
ll flow_to_push = 1;
current_total_flow += flow_to_push;
// Backtrack from sink t to source s to update flows and calculate the cost contribution of this path
int curr = t;
while (curr != s) {
int pv = prev_v[curr]; // Predecessor vertex
int edge_idx = prev_e[curr]; // Index of edge from pv used to reach curr
bool fwd = prev_fwd[curr]; // Was the edge used forward?
if (fwd) { // Edge pv -> curr was used forward
Edge &e = G[pv][edge_idx]; // The edge pv -> curr
// Calculate marginal cost based on flow *before* augmentation
ll marginal_cost = e.is_convex ? (1 - 2LL * e.P + 2LL * e.flow) : 0;
total_algo_cost += marginal_cost; // Add marginal cost to total cost
e.flow += flow_to_push; // Augment flow on the forward edge
} else { // Edge pv -> curr was used backward (meaning flow on curr -> pv was reduced)
Edge &rev_e = G[curr][G[pv][edge_idx].rev]; // The edge curr -> pv
// Calculate marginal cost for backward edge based on flow *before* augmentation
ll marginal_cost_backward = rev_e.is_convex ? (1 + 2LL * rev_e.P - 2LL * rev_e.flow) : 0;
total_algo_cost += marginal_cost_backward; // Add marginal cost to total cost
rev_e.flow -= flow_to_push; // Decrease flow on the edge curr -> pv
}
curr = pv; // Move to the previous node in the path
}
}
// The algorithm computes Sum(c(Q_ij) - c(0)). Return this value.
return total_algo_cost;
}
int main() {
ios_base::sync_with_stdio(false); // Faster I/O
cin.tie(NULL);
int N; // Matrix size N x N
ll K; // Total flow required
cin >> N >> K;
vector<ll> A(N), B(N); // Row sums A and column sums B
for (int i = 0; i < N; ++i) cin >> A[i];
for (int i = 0; i < N; ++i) cin >> B[i];
vector<vector<int>> P(N, vector<int>(N)); // Given matrix P
ll P_sq_sum = 0; // Calculate sum of squares of P elements, Sum P_ij^2
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
cin >> P[i][j];
P_sq_sum += (ll)P[i][j] * P[i][j];
}
}
// Setup the graph for min-cost flow problem
N_nodes = 2 * N + 2; // Total nodes: Source(1) + Rows(N) + Cols(N) + Sink(1)
int s = 0, t = 2 * N + 1; // Source node index 0, Sink node index 2N+1
G.assign(N_nodes, vector<Edge>()); // Initialize graph adjacency list
// Add edges from Source s=0 to Row nodes i+1 (indices 1 to N)
for (int i = 0; i < N; ++i) {
if (A[i] > 0) { // Optimization: only add edge if capacity A_i > 0
add_edge(s, i + 1, A[i]); // Capacity A_i, cost 0 (non-convex)
}
}
// Add edges from Column nodes N+1+j (indices N+1 to 2N) to Sink t=2N+1
for (int j = 0; j < N; ++j) {
if (B[j] > 0) { // Optimization: only add edge if capacity B_j > 0
add_edge(N + 1 + j, t, B[j]); // Capacity B_j, cost 0 (non-convex)
}
}
// Add edges from Row nodes i+1 to Column nodes N+1+j
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
// Capacity K is a safe upper bound on flow Q_ij.
add_edge(i + 1, N + 1 + j, K, P[i][j]); // Capacity K, convex cost based on P_ij
}
}
// Compute the minimum cost flow value which corresponds to Sum(c(Q_ij) - c(0))
ll min_cost_algo = min_cost_flow(s, t, K);
// The final answer is the minimum value of Sum (P_ij - Q_ij)^2 = Sum c(Q_ij)
// This equals min_cost_algo + Sum c(0) = min_cost_algo + P_sq_sum
cout << min_cost_algo + P_sq_sum << endl;
return 0;
}