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

BZOJ 1930 [SHOI2003] Pacman 吃豆豆 - 費用流優化建圖

編輯：關於C++

題目大意

平面上 n ≤ 2000 個點，兩個吃豆人從同一起點出發，只能往右上方移動 (即 x、y 皆不減)。每個點最多被吃一次。求兩人最多能吃到幾顆豆子。

基礎費用流模型 (會 TLE)

每點拆成 in/out，邊容量 1、費用 -1 (吃到豆子獲利)。
可達邊 out_i → in_j 容量 1、費用 0。
超級源 → 兩人起點容量 2、費用 0；所有 out → 超級匯容量 1、費用 0。
跑 MinCostMaxFlow，答案 = -minCost。
缺點：最壞 O(n²) 條邊 (全 (i,i) 點)，SPFA 會超時。

關鍵優化：傳遞性刪邊

若 i → j → k 可達，則 i → k 這條邊永不會被最優解使用 (繞路不如直接走 i→j→k)。

按 x 升序、y 升序排序後，對每個 i 只保留「y 單調遞增」的下一個可達點：

sort(pts+1, pts+n+1); // x 升，x 同則 y 升
for (int i = 1; i <= n; ++i) {
    int minY = INF;
    for (int j = i+1; j <= n; ++j) {
        if (pts[j].y >= pts[i].y && pts[j].y < minY) {
            addEdge(i_out, j_in, 2, 0); // 容量 2 因兩人皆可經過
            minY = pts[j].y;
        }
    }
}

邊數從 O(n²) 降至 O(n)，SPFA 極快。

完整優化代碼 (G++ 通過)

#include 
using namespace std;

struct MCMF {
    struct Edge { int to, nxt, cap, cost; };
    const int INF = 0x3f3f3f3f;
    vector head, dis, pre, pe;
    vector inq;
    vector e;
    int N, S, T, ecnt;

    MCMF(int n, int s, int t) : N(n), S(s), T(t) {
        head.assign(N, -1); dis.resize(N); pre.resize(N); pe.resize(N); inq.resize(N);
        ecnt = 0;
    }
    void addEdge(int u, int v, int cap, int cost) {
        e.push_back({v, head[u], cap, cost}); head[u] = ecnt++;
        e.push_back({u, head[v], 0, -cost}); head[v] = ecnt++;
    }
    bool spfa() {
        fill(dis.begin(), dis.end(), INF);
        fill(inq.begin(), inq.end(), false);
        queue q; q.push(S); dis[S] = 0; inq[S] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop(); inq[u] = false;
            for (int i = head[u]; ~i; i = e[i].nxt) {
                auto &ed = e[i];
                if (ed.cap && dis[ed.to] > dis[u] + ed.cost) {
                    dis[ed.to] = dis[u] + ed.cost;
                    pre[ed.to] = u; pe[ed.to] = i;
                    if (!inq[ed.to]) { inq[ed.to] = true; q.push(ed.to); }
                }
            }
        }
        return dis[T] != INF;
    }
    int minCostMaxFlow() {
        int cost = 0;
        while (spfa()) {
            int f = INF;
            for (int v = T; v != S; v = pre[v]) f = min(f, e[pe[v]].cap);
            for (int v = T; v != S; v = pre[v]) {
                e[pe[v]].cap -= f;
                e[pe[v]^1].cap += f;
            }
            cost += dis[T] * f;
        }
        return cost;
    }
};

struct Pt { int x, y; bool operator<(Pt o) const { return x==o.x? y> n;
    for (int i=1;i<=n;++i) cin >> p[i].x >> p[i].y;
    sort(p+1, p+n+1);

    int V = (n+2)*2 + 2;
    int S = 0, _S = 1, _T = V-2, T = V-1;
    MCMF mf(V, S, T);

    // 拆點 + 起終點連接
    for (int i=1;i<=n;++i) {
        int in = i<<1, out = i<<1|1;
        mf.addEdge(in, out, 1, -1); // 吃豆獲利
        mf.addEdge(in, out, 1, 0);  // 不吃也可通過
        mf.addEdge(_S, in, 1, 0);
        mf.addEdge(out, _T, 1, 0);
    }
    mf.addEdge(S, _S, 2, 0);
    mf.addEdge(_T, T, 2, 0);

    // 傳遞性刪邊
    for (int i=1;i<=n;++i) {
        int minY = INT_MAX;
        for (int j=i+1;j<=n;++j) {
            if (p[j].y >= p[i].y && p[j].y < minY) {
                mf.addEdge((i<<1|1), (j<<1), 2, 0);
                minY = p[j].y;
            }
        }
    }

    cout << -mf.minCostMaxFlow() << '\n';
    return 0;
}