제출 #1163694

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163694		monkey133	Rainy Markets (CCO22_day1problem2)	C++20	0 / 25	0 ms	328 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <cassert>
#include <algorithm>
using namespace std;

#define int long long

typedef long long ll;
const ll INF = 1e18;

// Edge structure for our min-cost flow graph.
struct Edge {
    int to, rev;    // 'to' is the destination node, 'rev' is the index of the reverse edge.
    ll cap, cost;   // 'cap' is the capacity, 'cost' is the cost per unit of flow.
    ll orig;        // Original capacity (used later to extract the assignment).
};

struct MinCostFlow {
    int n; // number of nodes in the graph
    vector<vector<Edge>> graph;
    vector<ll> dist, potential;
    vector<int> parent, parentEdge;

    MinCostFlow(int n) : n(n), graph(n), dist(n), potential(n), parent(n), parentEdge(n) { }

    // Adds a directed edge from node s to node t with capacity 'cap' and cost 'cost'.
    void addEdge(int s, int t, ll cap, ll cost) {
        Edge a = { t, (int)graph[t].size(), cap, cost, cap };
        Edge b = { s, (int)graph[s].size(), 0, -cost, 0 };
        graph[s].push_back(a);
        graph[t].push_back(b);
    }

    // Computes the min-cost flow from s to t, sending at most 'f' units.
    // Returns a pair {flow, total cost}.
    pair<ll, ll> minCostFlow(int s, int t, ll f) {
        ll flow = 0, cost = 0;
        // Initialize potentials (for reduced costs) to 0.
        fill(potential.begin(), potential.end(), 0);
        while (flow < f) {
            // Use Dijkstra's algorithm to find the shortest (adjusted) path from s to t.
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
            pq.push({0, s});
            while(!pq.empty()){
                auto [d, v] = pq.top();
                pq.pop();
                if(d != dist[v]) continue;
                for (int i = 0; i < graph[v].size(); i++){
                    Edge &e = graph[v][i];
                    if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + potential[v] - potential[e.to]){
                        dist[e.to] = dist[v] + e.cost + potential[v] - potential[e.to];
                        parent[e.to] = v;
                        parentEdge[e.to] = i;
                        pq.push({dist[e.to], e.to});
                    }
                }
            }
            if(dist[t] == INF) break; // No path exists; not all flow can be sent.
            // Update potentials.
            for (int i = 0; i < n; i++){
                if(dist[i] < INF)
                    potential[i] += dist[i];
            }
            // Determine the maximum additional flow we can send along the path.
            ll addFlow = f - flow;
            for (int v = t; v != s; v = parent[v]){
                addFlow = min(addFlow, graph[parent[v]][parentEdge[v]].cap);
            }
            flow += addFlow;
            cost += addFlow * potential[t];
            // Update the capacities along the path.
            for (int v = t; v != s; v = parent[v]){
                Edge &e = graph[parent[v]][parentEdge[v]];
                e.cap -= addFlow;
                graph[v][e.rev].cap += addFlow;
            }
        }
        return {flow, cost};
    }
};

//
// Main: Reads input, builds the flow network, runs the min-cost flow algorithm, and prints output.
//
// Input Specification:
//  - First line: integer N (number of bus shelters).
//  - Second line: N space-separated integers B[1..N] (capacity of each bus shelter).
//  - Third line: N-1 space-separated integers P[1..N-1] (number of people at market i).
//  - Fourth line: N-1 space-separated integers U[1..N-1] (umbrellas available at market i).
//
// Output Specification:
//  - If every person can stay dry, output N+1 lines:
//      YES
//      <minimum umbrella cost>
//      For each market i (1 to N-1), output three integers:
//         <# going to bus shelter i> <# buying umbrella> <# going to bus shelter i+1>
//  - Otherwise, output a single line: NO
//
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vector<ll> B(N+1);
    for (int i = 1; i <= N; i++){
        cin >> B[i];
    }
    int M = N - 1;  // Markets are numbered 1..N-1.
    vector<ll> P(M+1), U(M+1);
    for (int i = 1; i <= M; i++){
        cin >> P[i];
    }
    for (int i = 1; i <= M; i++){
        cin >> U[i];
    }

    // Build our flow network with the following node layout:
    //   Node 0: Source (S)
    //   Nodes 1 .. M: Markets (market i is node i)
    //   Nodes M+1 .. M+N: Bus shelters (bus shelter i is at node M + i)
    //   Node M+N+1: Sink (T)
    int S = 0;
    int marketStart = 1;
    int busStart = marketStart + M;  // Bus shelter nodes start at busStart.
    int T = busStart + N;
    int totalNodes = T + 1;

    MinCostFlow mcf(totalNodes);

    // Total number of people in all markets.
    ll totalPeople = 0;
    for (int i = 1; i <= M; i++){
        totalPeople += P[i];
    }

    // 1. Add edges from source S to each market i.
    for (int i = 1; i <= M; i++){
        mcf.addEdge(S, i, P[i], 0);
    }

    // 2. For each market i, add three edges:
    //    - Edge to bus shelter i ("left" option): node busStart + (i-1)
    //    - Edge to bus shelter i+1 ("right" option): node busStart + i
    //    - Edge to sink T (buy umbrella): capacity U[i], cost 1
    for (int i = 1; i <= M; i++){
        mcf.addEdge(i, busStart + (i - 1), P[i], 0); // Left option.
        mcf.addEdge(i, busStart + i, P[i], 0);         // Right option.
        mcf.addEdge(i, T, U[i], 1);                      // Umbrella option.
    }

    // 3. For each bus shelter i, add an edge from the bus shelter node to sink T with capacity B[i] and cost 0.
    for (int i = 1; i <= N; i++){
        mcf.addEdge(busStart + (i - 1), T, B[i], 0);
    }

    // Run the min-cost flow algorithm.
    auto res = mcf.minCostFlow(S, T, totalPeople);

    // Check if we could send all people from the markets.
    if (res.first < totalPeople) {
        cout << "NO\n";
        return 0;
    }

    // Otherwise, print the result.
    cout << "YES\n" << res.second << "\n";
    // For each market i, extract flows on the three edges:
    //   index 0: Market i -> bus shelter i ("left")
    //   index 1: Market i -> bus shelter i+1 ("right")
    //   index 2: Market i -> sink T ("umbrella")
    for (int i = 1; i <= M; i++){
        assert(mcf.graph[i].size() >= 3);
        ll left_flow = mcf.graph[i][0].orig - mcf.graph[i][0].cap;
        ll right_flow = mcf.graph[i][1].orig - mcf.graph[i][1].cap;
        ll umb_flow = mcf.graph[i][2].orig - mcf.graph[i][2].cap;
        cout << left_flow << " " << umb_flow << " " << right_flow << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 6
• Subtask 4: 0 / 9