結果
問題 |
No.1341 真ん中を入れ替えて門松列
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:13:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 9,010 bytes |
コンパイル時間 | 892 ms |
コンパイル使用メモリ | 92,872 KB |
実行使用メモリ | 491,296 KB |
最終ジャッジ日時 | 2025-05-14 13:14:42 |
合計ジャッジ時間 | 4,746 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 2 TLE * 1 -- * 11 |
ソースコード
#include <iostream> #include <vector> #include <queue> #include <limits> #include <algorithm> // Use long long for costs and potentially large sums using CostType = long long; // Use a large enough value for infinity, ensuring it doesn't overflow during calculations // std::numeric_limits<long long>::max() is about 9e18. Dividing by 4 should be safe. const CostType INF_COST = std::numeric_limits<CostType>::max() / 4; // Structure to represent an edge in the residual graph struct Edge { int to; // destination vertex int capacity; // residual capacity int reverse_edge_idx; // index of the reverse edge in the adjacency list of 'to' vertex CostType cost; // cost of pushing 1 unit of flow through this edge }; // Adjacency list representation of the graph std::vector<std::vector<Edge>> graph; // Potentials for Dijkstra algorithm (to handle negative costs) std::vector<CostType> h; // Shortest distance estimates from source std::vector<CostType> dist; // Store path information for augmentation: previous vertex and index of edge used to reach current vertex std::vector<int> prev_v, prev_e_idx; // Function to add an edge and its corresponding reverse edge to the graph void add_edge(int u, int v, int cap, CostType cost) { // Add edge from u to v graph[u].push_back({v, cap, (int)graph[v].size(), cost}); // Add reverse edge from v to u. Initial capacity is 0. Cost is negated. graph[v].push_back({u, 0, (int)graph[u].size() - 1, -cost}); } // Compute Minimum Cost Flow from source 's' to sink 't' with required flow 'f' // Uses Dijkstra with potentials based on Successive Shortest Path algorithm // Returns the minimum cost to achieve flow 'f', or a large value (INF_COST * 2) if flow 'f' cannot be achieved. CostType min_cost_flow(int s, int t, int f) { CostType total_cost = 0; // Accumulates the total minimum cost int V = graph.size(); // Number of vertices in the graph h.assign(V, 0); // Initialize potentials to 0 int flow_pushed = 0; // Keep track of the total flow pushed so far // Continue augmenting paths until the required flow 'f' is achieved while (flow_pushed < f) { // Initialize distances to infinity for all vertices dist.assign(V, INF_COST); // Initialize predecessors for path reconstruction prev_v.assign(V, -1); prev_e_idx.assign(V, -1); dist[s] = 0; // Distance from source to itself is 0 // Priority queue for Dijkstra. Stores pairs {distance, vertex}. Ordered by distance. std::priority_queue<std::pair<CostType, int>, std::vector<std::pair<CostType, int>>, std::greater<std::pair<CostType, int>>> pq; pq.push({0, s}); // Start Dijkstra from source while (!pq.empty()) { // Extract vertex 'u' with the smallest distance 'd' CostType d = pq.top().first; int u = pq.top().second; pq.pop(); // If we found a shorter path to 'u' already, skip this element if (d > dist[u]) continue; // Explore neighbors of 'u' for (size_t i = 0; i < graph[u].size(); ++i) { Edge &e = graph[u][i]; // Check if edge has residual capacity if (e.capacity > 0) { // Calculate reduced cost: cost' = original_cost + potential[u] - potential[v] CostType reduced_cost = e.cost + h[u] - h[e.to]; // If found a shorter path to e.to using edge e if (dist[e.to] > dist[u] + reduced_cost) { dist[e.to] = dist[u] + reduced_cost; // Update distance prev_v[e.to] = u; // Store predecessor prev_e_idx[e.to] = i; // Store edge index pq.push({dist[e.to], e.to}); // Add/update neighbor in priority queue } } } } // If sink 't' is unreachable from 's' in the residual graph, we cannot push more flow if (dist[t] == INF_COST) { // Cannot satisfy the required flow 'f' return INF_COST * 2; // Return a large value indicating failure } // Update potentials using the shortest path distances found by Dijkstra // h[v] += dist[v] maintains non-negative reduced costs for the next iteration for (int v = 0; v < V; ++v) { if (dist[v] != INF_COST) { // Only update potentials for reachable vertices h[v] += dist[v]; } } // Determine the bottleneck capacity ('flow_on_path') along the shortest path found int flow_on_path = f - flow_pushed; // Maximum flow we need is the remaining required flow // Trace back path from t to s to find bottleneck capacity for (int v = t; v != s; v = prev_v[v]) { flow_on_path = std::min(flow_on_path, graph[prev_v[v]][prev_e_idx[v]].capacity); } // Increase total flow pushed flow_pushed += flow_on_path; // Add the cost of pushing 'flow_on_path' units along this path to the total cost. // The cost of the path in terms of original costs is given by the potential difference h[t] - h[s]. Since h[s] remains 0, it's just h[t]. total_cost += (CostType)flow_on_path * h[t]; // Update residual capacities along the path and reverse edges for (int v = t; v != s; v = prev_v[v]) { Edge &e = graph[prev_v[v]][prev_e_idx[v]]; e.capacity -= flow_on_path; // Decrease capacity of forward edge graph[v][e.reverse_edge_idx].capacity += flow_on_path; // Increase capacity of reverse edge } } // Successfully pushed flow 'f' return total_cost; } int main() { // Faster I/O std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int N; // Number of triplets long long M; // Threshold for Kadomatsu point sum std::cin >> N >> M; // Store input triplets A, B, C values std::vector<long long> A(N), C(N); std::vector<long long> B(N); for (int i = 0; i < N; ++i) { std::cin >> A[i] >> B[i] >> C[i]; } // Set up the flow network graph // V = total vertices: Source (0) + N slot nodes (1..N) + N value nodes (N+1..2N) + Sink (2N+1) int V = 2 * N + 2; graph.resize(V); int s = 0, t = 2 * N + 1; // Source and sink node indices // Add edges from source to slot nodes // Each slot node corresponds to a triplet (A_i, ?, C_i) for (int i = 0; i < N; ++i) { add_edge(s, i + 1, 1, 0); // Capacity 1, Cost 0 } // Add edges from value nodes to sink // Each value node corresponds to a B_j value for (int j = 0; j < N; ++j) { add_edge(N + 1 + j, t, 1, 0); // Capacity 1, Cost 0 } // Add edges between slot nodes and value nodes if the assignment forms a Kadomatsu sequence for (int i = 0; i < N; ++i) { // Slot i corresponds to node i+1 long long min_AC = std::min(A[i], C[i]); long long max_AC = std::max(A[i], C[i]); for (int j = 0; j < N; ++j) { // Value B[j] corresponds to node N+1+j // Check Kadomatsu condition: B[j] must be outside the interval [min(A[i], C[i]), max(A[i], C[i])] if (B[j] < min_AC) { // Condition met: B[j] < min(A[i], C[i]) // Kadomatsu point is max(A[i], B[j], C[i]) = max(A[i], C[i]) = max_AC CostType weight = max_AC; add_edge(i + 1, N + 1 + j, 1, -weight); // Use negative weight because we want to maximize total weight via min cost flow } else if (B[j] > max_AC) { // Condition met: B[j] > max(A[i], C[i]) // Kadomatsu point is max(A[i], B[j], C[i]) = B[j] CostType weight = B[j]; add_edge(i + 1, N + 1 + j, 1, -weight); // Use negative weight } // If B[j] is within [min_AC, max_AC], it's not a Kadomatsu sequence, so no edge is added. } } // Calculate minimum cost for achieving flow N (which corresponds to a perfect matching) CostType min_total_cost = min_cost_flow(s, t, N); // Check if it was possible to achieve flow N (i.e., find a perfect matching) if (min_total_cost >= INF_COST * 2) { // Check against the failure indicator value // A perfect matching doesn't exist. Output NO. std::cout << "NO" << std::endl; } else { // A perfect matching exists. Output YES. std::cout << "YES" << std::endl; // Maximum total weight is the negation of the minimum cost found long long max_total_weight = -min_total_cost; // Check if the maximum weight meets the threshold M if (max_total_weight >= M) { std::cout << "KADOMATSU!" << std::endl; } else { std::cout << "NO" << std::endl; } } return 0; }