結果

問題 No.1615 Double Down
ユーザー qwewe
提出日時 2025-05-14 13:20:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,199 bytes
コンパイル時間 1,546 ms
コンパイル使用メモリ 103,604 KB
実行使用メモリ 25,712 KB
最終ジャッジ日時 2025-05-14 13:22:25
合計ジャッジ時間 24,305 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>

// Use long long for costs and total sum as prices can be large (2^30)
// and sum of prices can exceed 32-bit integer limit.
const long long INF = 1e18; // A large enough value for infinity

struct Edge {
    int to;         // Destination vertex
    int capacity;   // Capacity of the edge
    int flow;       // Current flow through the edge
    long long cost; // Cost per unit of flow
    int rev;        // Index of the reverse edge in adj[to]
};

std::vector<std::vector<Edge>> adj; // Adjacency list for the graph
std::vector<long long> dist;        // Shortest distance from source in SPFA
std::vector<int> parent_v;          // Parent vertex in shortest path
std::vector<int> parent_e;          // Parent edge index in shortest path
int V_flow;                         // Total number of vertices in the flow network

// Adds an edge and its residual edge
void add_edge(int u, int v, int cap, long long cost) {
    adj[u].push_back({v, cap, 0, cost, (int)adj[v].size()});
    adj[v].push_back({u, 0, 0, -cost, (int)adj[u].size() - 1}); // Residual edge for 0 cap initially
}

// Min-cost max-flow algorithm using SPFA
// Finds paths and augments flow as long as it reduces total cost (increases profit)
// total_flow_val will store the number of matched pairs.
long long min_cost_max_flow_calc(int s, int t, int& total_flow_val) {
    long long total_cost = 0;
    total_flow_val = 0;

    dist.resize(V_flow);
    parent_v.resize(V_flow);
    parent_e.resize(V_flow);

    while (true) {
        std::fill(dist.begin(), dist.end(), INF);
        dist[s] = 0;
        std::vector<bool> in_queue(V_flow, false);
        std::queue<int> q;

        q.push(s);
        in_queue[s] = true;

        // SPFA to find shortest path in terms of cost
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            in_queue[u] = false;

            for (int i = 0; i < adj[u].size(); ++i) {
                Edge& e = adj[u][i];
                if (e.capacity - e.flow > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    parent_v[e.to] = u;
                    parent_e[e.to] = i;
                    if (!in_queue[e.to]) {
                        q.push(e.to);
                        in_queue[e.to] = true;
                    }
                }
            }
        }

        // If no path found, or path found has non-negative cost (no more profit)
        if (dist[t] == INF || dist[t] >= 0) { 
            // dist[t] >= 0 means we can't add more items to increase profit
            // (as costs are -price, so positive cost means negative profit)
            break;
        }

        // All edge capacities for matching are 1. So path_flow is 1.
        int path_flow = 1; 
        
        total_flow_val += path_flow; // One more item matched
        total_cost += (long long)path_flow * dist[t]; // Add cost of this path to total

        // Augment flow along the path
        int cur = t;
        while (cur != s) {
            int prev = parent_v[cur];
            int edge_idx = parent_e[cur];
            adj[prev][edge_idx].flow += path_flow;
            adj[cur][adj[prev][edge_idx].rev].flow -= path_flow; // Update flow on reverse edge
            cur = prev;
        }
    }
    return total_cost;
}

struct BidInfo {
    int x_orig, y_orig, z; // Original buyer ID, item ID, and Z value
    long long price;       // Calculated price 2^Z
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N_max, M_max, K_val, L_bids; // Max IDs N, M, max power K, num_bids L
    std::cin >> N_max >> M_max >> K_val >> L_bids;

    std::vector<BidInfo> bids(L_bids);
    std::map<int, int> buyer_orig_to_idx; // Map original buyer ID to 0-indexed internal ID
    std::map<int, int> item_orig_to_idx;  // Map original item ID to 0-indexed internal ID
    int next_buyer_idx = 0;
    int next_item_idx = 0;

    for (int i = 0; i < L_bids; ++i) {
        std::cin >> bids[i].x_orig >> bids[i].y_orig >> bids[i].z;
        bids[i].price = (1LL << bids[i].z); // Price is 2^Z

        // Assign new compact index if this buyer/item ID is seen for the first time
        if (buyer_orig_to_idx.find(bids[i].x_orig) == buyer_orig_to_idx.end()) {
            buyer_orig_to_idx[bids[i].x_orig] = next_buyer_idx++;
        }
        if (item_orig_to_idx.find(bids[i].y_orig) == item_orig_to_idx.end()) {
            item_orig_to_idx[bids[i].y_orig] = next_item_idx++;
        }
    }

    int num_actual_buyers = next_buyer_idx;
    int num_actual_items = next_item_idx;

    // Define source and sink nodes for the flow network
    // Buyers: 0 to num_actual_buyers-1
    // Items: num_actual_buyers to num_actual_buyers + num_actual_items - 1
    int s_node = num_actual_buyers + num_actual_items;     // Source node index
    int t_node = num_actual_buyers + num_actual_items + 1; // Sink node index
    V_flow = num_actual_buyers + num_actual_items + 2;   // Total vertices in flow network
    
    adj.assign(V_flow, std::vector<Edge>()); // Initialize adjacency list

    // Edges from source to buyers
    for (int i = 0; i < num_actual_buyers; ++i) {
        add_edge(s_node, i, 1, 0); // cap 1, cost 0
    }
    // Edges from items to sink
    for (int i = 0; i < num_actual_items; ++i) {
        // Item node index is i (0 to num_actual_items-1) + num_actual_buyers
        add_edge(num_actual_buyers + i, t_node, 1, 0); // cap 1, cost 0
    }

    // Edges from buyers to items for each bid
    for (const auto& bid : bids) {
        int u_compact_idx = buyer_orig_to_idx[bid.x_orig];
        int v_compact_idx = item_orig_to_idx[bid.y_orig] + num_actual_buyers; // Offset item indices
        add_edge(u_compact_idx, v_compact_idx, 1, -bid.price); // cap 1, cost -price
    }
    
    int total_flow = 0; // Will store total number of items sold
    long long min_total_cost = min_cost_max_flow_calc(s_node, t_node, total_flow);

    // Max revenue is -min_total_cost (because costs were negative prices)
    std::cout << -min_total_cost << std::endl;

    return 0;
}
0