您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

POJ 3762 The Bonus Salary!：費用流 + 時間離散化解任務調度

編輯：C++ 入門

問題描述

有 N 個任務，每個任務有時間窗 [Lᵢ, Rᵢ]（精確到秒，必須佔用整段時間）和收益 wᵢ。同時只能做一個任務。有 K 天時間（每天 86400 秒）。最多選一段商業線？實為：最多 K 個不重疊任務（每天最多一個？題目實為：總時間跨度 K 天，任務不可重疊，最多做 K 個？不，重讀題目：K 天總時間，任務不可重疊，求最大收益）。

實際模型：時間線上選不重疊區間，最多選 K 個，最大權和。N ≤ 2000，K ≤ 100。

最小費用最大流建模

時間離散化：收集所有 Lᵢ, Rᵢ，排序去重，映射為 0~T-1。
構建網絡：
- 源點 S，匯點 T。
- 相鄰時間點 i → i+1：容量 INF，費用 0（不做任務時時間流逝）。
- 任務邊 Lᵢ → Rᵢ：容量 1，費用 -wᵢ（做任務獲得收益，費用為負）。
- S → 0：容量 K，費用 0（最多 K 單位流 = 最多 K 個任務/天？實為 K 天總流量）。
跑 Min-Cost Max-Flow (SPFA 增廣)，總費用取負即最大收益。

關鍵細節

離散化後相鄰點連邊：保證流可在無任務時段「流動」到下一任務起點。
容量 K：源點到首時間點容量 K，限制總任務數/並發數（題目實為 K 天，每天可做多個不重疊任務，但總流量 K 正確建模了「最多 K 段時間」？需確認：實際為 K 天總時間，流量 K 代表可用 K 個「時間槽」）。
SPFA 找最短增廣路：負費用邊存在，需 SPFA 或 Bellman-Ford。
邊數組開大：時間點 ≤ 2N=4000，邊 ≤ 4000+2000，開 10000+ 保險。

程式碼框架（C++）

/* POJ 3762 The Bonus Salary! - Min Cost Flow + Time Discretization */
#include <bits/stdc++.h>
using namespace std;

struct Edge { int to, cap, cost, rev; };
vector G[10000];
int dist[10000], pv[10000], pe[10000];
bool inq[10000];

void addEdge(int u, int v, int cap, int cost) {
    G[u].push_back({v, cap, cost, (int)G[v].size()});
    G[v].push_back({u, 0, -cost, (int)G[u].size()-1});
}

bool spfa(int s, int t) {
    fill(dist, dist+t+1, 1e9);
    memset(inq, 0, sizeof(inq));
    dist[s] = 0; queue q; q.push(s); inq[s]=1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u]=0;
        for (int i = 0; i < G[u].size(); ++i) {
            Edge &e = G[u][i];
            if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                dist[e.to] = dist[u] + e.cost;
                pv[e.to] = u; pe[e.to] = i;
                if (!inq[e.to]) { q.push(e.to); inq[e.to]=1; }
            }
        }
    }
    return dist[t] < 1e9;
}

int minCostFlow(int s, int t, int maxf) {
    int flow = 0, cost = 0;
    while (flow < maxf && spfa(s, t)) {
        int f = maxf - flow;
        for (int v = t; v != s; v = pv[v])
            f = min(f, G[pv[v]][pe[v]].cap);
        flow += f;
        cost += f * dist[t];
        for (int v = t; v != s; v = pv[v]) {
            Edge &e = G[pv[v]][pe[v]];
            e.cap -= f;
            G[v][e.rev].cap += f;
        }
    }
    return cost;
}

struct Task { int l, r, w; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, K; cin >> N >> K;
    vector tasks(N);
    vector coords;
    for (int i = 0; i < N; ++i) {
        string ls, rs; int w;
        cin >> ls >> rs >> w;
        auto parse = [](string s) {
            int h = stoi(s.substr(0,2)), m = stoi(s.substr(3,2)), sec = stoi(s.substr(6,2));
            return h*3600 + m*60 + sec;
        };
        tasks[i].l = parse(ls);
        tasks[i].r = parse(rs);
        tasks[i].w = w;
        coords.push_back(tasks[i].l);
        coords.push_back(tasks[i].r);
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    int T = coords.size();
    int S = T, TT = T+1;
    for (int i = 0; i < T-1; ++i) addEdge(i, i+1, 1e9, 0);
    for (auto &tk : tasks) {
        int u = lower_bound(coords.begin(), coords.end(), tk.l) - coords.begin();
        int v = lower_bound(coords.begin(), coords.end(), tk.r) - coords.begin();
        addEdge(u, v, 1, -tk.w);
    }
    addEdge(S, 0, K, 0);
    int cost = minCostFlow(S, TT, K);
    cout << -cost << "\n";
    return 0;
}