POJ 3469 Dual Core CPU：最小割模型分配任務到雙核

題目大意

有 n 個任務，可在 CPU A 或 B 上運行，耗時分別為 a_i, b_i。m 對任務若分配到不同 CPU 產生額外開銷 w。求最小總開銷。

最小割建模

源點 S 代表 CPU A，匯點 T 代表 CPU B。
- S → i 容量 a_i（割掉表示分配給 B）。
- i → T 容量 b_i（割掉表示分配給 A）。
- 任務對 (u,v) 若分在不同 CPU 付出 w：添加 u → v 和 v → u 容量 w 的邊。若 u,v 分屬兩側，必割斷其中一條，產生費用 w。
最小割即最小總開銷。

Dinic 算法實現

節點數 n+2 ≤ 20002，邊數 2n + 4m ≤ 100000，Dinic O(E√V) 足夠快。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct Dinic {
    struct Edge { int to, rev, cap; };
    int N, S, T; vector> G;
    vector level, it;
    Dinic(int n): N(n), G(n), level(n), it(n) {}
    void addEdge(int u, int v, int cap) {
        Edge a{v, (int)G[v].size(), cap};
        Edge b{u, (int)G[u].size(), 0};
        G[u].push_back(a); G[v].push_back(b);
    }
    bool bfs() {
        fill(level.begin(), level.end(), -1);
        queue q; q.push(S); level[S] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& e : G[u]) if (e.cap > 0 && level[e.to] == -1) {
                level[e.to] = level[u] + 1; q.push(e.to);
            }
        }
        return level[T] != -1;
    }
    int dfs(int u, int f) {
        if (u == T) return f;
        for (int& i = it[u]; i < G[u].size(); ++i) {
            Edge& e = G[u][i];
            if (e.cap > 0 && level[e.to] == level[u] + 1) {
                int ret = dfs(e.to, min(f, e.cap));
                if (ret) { e.cap -= ret; G[e.to][e.rev].cap += ret; return ret; }
            }
        }
        return 0;
    }
    int maxflow(int s, int t) {
        S = s; T = t; int flow = 0;
        while (bfs()) {
            fill(it.begin(), it.end(), 0);
            while (int f = dfs(S, INF)) flow += f;
        }
        return flow;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        Dinic mf(n + 2);
        int S = 0, T = n + 1;
        for (int i = 1; i <= n; ++i) {
            int a, b; cin >> a >> b;
            mf.addEdge(S, i, a);
            mf.addEdge(i, T, b);
        }
        for (int i = 0; i < m; ++i) {
            int u, v, w; cin >> u >> v >> w;
            mf.addEdge(u, v, w);
            mf.addEdge(v, u, w);
        }
        cout << mf.maxflow(S, T) << '\n';
    }
    return 0;
}

關鍵點

• 雙向添加 u→v 和 v→u 容量 w，確保不同側時割集包含該費用。
• 源點連 A 耗時，匯點連 B 耗時，割集自然對應分配方案。