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

POJ 3680 Intervals - 費用流解決區間選擇最大權重問題

編輯：關於C++

問題描述

給定 N 個加權開區間 (a_i, b_i)，權重 w_i。選擇若干區間使得總權重最大，約束：實數軸上任意點被覆蓋次數不超過 K。N ≤ 200，坐標 ≤ 100,000。

核心建模：最小費用最大流

將問題轉化為網絡流模型：

離散化座標：收集所有端點 a_i, b_i，排序去重，映射為 1..M
構建鏈狀圖：相鄰離散點 i → i+1 連邊，容量 K，費用 0（保證任意點覆蓋 ≤ K）
區間邊：每個區間 [a_i, b_i] 連邊 a_i → b_i，容量 1，費用 -w_i（選擇區間獲得收益）
源匯點：超級源 S → 1，超級匯 M → T，容量 K，費用 0

為什麼這樣建模是正確的？

鏈狀邊 i→i+1 容量 K 限制了通過該段「流量」≤ K，對應覆蓋次數限制
區間邊 a→b 繞過中間鏈狀邊，攜帶負費用（收益），流經它代表選擇該區間
最小費用流會自動選擇「性價比最高」的區間組合

SPFA + Dinic 最小費用流模板

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int INF = 1e9;
struct Edge { int to, next, cap, cost; } e[100000];
int head[500], dis[500], pre[500], cur[500];
bool inq[500];
int cnt = 1, N, K, S, T;

void addEdge(int u, int v, int cap, int cost) {
    e[++cnt] = {v, head[u], cap, cost}; head[u] = cnt;
    e[++cnt] = {u, head[v], 0, -cost}; head[v] = cnt;
}

bool spfa() {
    fill(dis, dis + T + 1, INF);
    memset(inq, 0, sizeof(inq));
    queue q; q.push(S); dis[S] = 0; inq[S] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (e[i].cap && dis[v] > dis[u] + e[i].cost) {
                dis[v] = dis[u] + e[i].cost;
                pre[v] = i;
                if (!inq[v]) { q.push(v); inq[v] = 1; }
            }
        }
    }
    return dis[T] != INF;
}

int minCostMaxFlow() {
    int flow = 0, cost = 0;
    while (spfa()) {
        int f = INF;
        for (int i = pre[T]; i; i = pre[e[i^1].to]) 
            f = min(f, e[i].cap);
        for (int i = pre[T]; i; i = pre[e[i^1].to]) {
            e[i].cap -= f;
            e[i^1].cap += f;
        }
        flow += f;
        cost += f * dis[T];
    }
    return -cost;  // 費用為負，取相反數得最大權重
}

int main() {
    int tcases; scanf("%d", &tcases);
    while (tcases--) {
        memset(head, 0, sizeof(head));
        cnt = 1;
        scanf("%d%d", &N, &K);
        
        int a[205], b[205], w[205];
        int coords[405], cc = 0;
        for (int i = 1; i <= N; ++i) {
            scanf("%d%d%d", &a[i], &b[i], &w[i]);
            coords[++cc] = a[i];
            coords[++cc] = b[i];
        }
        
        // 離散化
        sort(coords + 1, coords + cc + 1);
        int M = unique(coords + 1, coords + cc + 1) - coords - 1;
        map mp;
        for (int i = 1; i <= M; ++i) mp[coords[i]] = i;
        
        S = M + 1; T = M + 2;
        // 鏈狀邊
        for (int i = 1; i < M; ++i) addEdge(i, i+1, K, 0);
        addEdge(S, 1, K, 0);
        addEdge(M, T, K, 0);
        // 區間邊
        for (int i = 1; i <= N; ++i) 
            addEdge(mp[a[i]], mp[b[i]], 1, -w[i]);
        
        printf("%d\n", minCostMaxFlow());
    }
    return 0;
}