結果

問題 No.1341 真ん中を入れ替えて門松列
ユーザー qwewe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
}
0