CSU 1319 CX's Dreams：最大權閉合圖求最多正權點數

CSU 1319 CX's Dreams：最大權閉合圖求最多正權點數

給定夢想與工作的依賴關係，夢想有正權值，工作有正負權值。選擇夢想需完成前置工作。求最大權值和，並在最大權值下求最多正權夢想個數。轉化為最大權閉合子圖問題。

模型構建

• 源點 S 連向夢想節點，容量 = dream[i] * C + 1（C=1e6 大常數）。
• 工作節點連向匯點 T，若 容量 = -work[i] * C；若 直接加入答案，不連邊。
• 夢想 i 依賴工作 u，連邊 i → n+u，容量 INF。

雙重目標處理技巧

將點權擴展為 weight * C + (weight>0 ? 1 : 0)。最大流 flow 滿足：

• flow / C = 最大權值損失（總正權 - 最大權閉合圖權值）。
• flow % C = 被迫放棄的正權點數。

最終答案：

• 最大權值 = totalPositive - flow / C。
• 最多正權點數 = positiveCount - flow % C。

Dinic 最大流模板（長整型）

typedef long long ll;
const int N = 3010, M = 500010;
const ll INF = 1e18;

template<class T> struct Max_Flow {
    int n, Q[N], sign;
    int head[N], level[N], cur[N], pre[N];
    int nxt[M], pnt[M], E;
    T cap[M];
    void Init(int n) { this->n = n+1; E=0; fill(head, head+n, -1); }
    void add(int u, int v, T c, T rw=0) { ... }  // 標準加邊
    bool Bfs(int s, int t) { ... }  // 分層
    void Push(int t, T &flow) { ... }  // 增廣
    void Dfs(int u, int t, T &flow) { ... }  // 尋找增廣路
    T Dinic(int s, int t) { ... }  // 主流程
};

主程序邏輯

const ll C = 1e6;
void input() {
    ans = 0; from = 0; to = n+m+1;
    F.Init(to);
    for (i=1; i<=n; i++) {
        scanf("%lld", &dream[i]);
        F.add(from, i, dream[i]*C + 1, 0);
        ans += dream[i];
    }
    for (i=1; i<=m; i++) {
        scanf("%lld", &work[i]);
        if (work[i] >= 0) ans += work[i];
        else F.add(n+i, to, -work[i]*C, 0);
    }
    for (i=1; i<=n; i++) {
        scanf("%d", &siz);
        while (siz--) {
            scanf("%d", &u);
            if (work[u] >= 0) continue;
            F.add(i, n+u, INF, 0);
        }
    }
}

int main() {
    while (~scanf("%d%d", &n, &m)) {
        input();
        ll flow = F.Dinic(from, to);
        cout << ans - flow/C << " " << n - flow%C << endl;
    }
    return 0;
}

關鍵點

• C=1e6 需大於最大可能正權點數（n≤3000），保證 flow/C、flow%C 不干擾。
• 正權工作直接加入 ans，不進網絡，簡化圖結構。
• 依賴邊容量 INF 強制選擇夢想必選工作。

複雜度

• Dinic O(V²E)，實際極快（V≈6000, E≈500000）。
• 長整型防止 C * weight 溢出。

此題展示了最大權閉合圖建模與「大常數編碼雙目標」的高級技巧，是網絡流解決組合優化問題的經典範例。