SPOJ 1476 Maximum Profit：最大權閉合子圖解析與 ISAP 最大流實現

問題背景：最大權閉合子圖

在圖論中，「最大權閉合子圖」是指在一個有向圖中，找到一個點權總和最大的閉合子圖。所謂閉合子圖，即若某個節點被選入子圖，則其所有出邊指向的節點也必須被選入。這類問題常見於項目選擇、任務調度等場景，可轉化為網絡流中的最小割問題求解。

建模思路：從閉合子圖到最小割

構建流網絡的步驟如下：

• 源點 S 向所有正權點 v (w_v > 0) 連邊，容量為 w_v；
• 所有負權點 v (w_v < 0) 向匯點 T 連邊，容量為 -w_v；
• 原圖中的每條有向邊轉化為容量為無窮大（INF）的邊；
• 零權點不與源、匯相連。

此時，最大權閉合子圖的權值 = 所有正權點權值之和 - 最小割容量 = SUM - 最大流。

核心代碼：ISAP 最大流算法實現

以下採用 ISAP（改進的最短增廣路算法）求解最大流，具有 O(V^2 E) 的最壞情況複雜度，實際運行極快。

/* 
 * Author: yew1eb
 * Created Time: 2014年10月31日 星期五 15時39分22秒
 * File Name: spoj1476 maximum profit.cpp
 */
#include <ctime>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;

typedef long long ll;
const int inf = 1e9;
const ll INF = 1e18;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int maxn = 60010;
const int maxm = 2000010;

struct Edge {
    int to, cap, next;
    Edge(int _next=0, int _to=0, int _cap=0): next(_next), to(_to), cap(_cap) {}
} edge[maxm];

int n, m, S, T, cnt;
int head[maxn], tot;
int d[maxn];   // 到匯點的距離下界
int gap[maxn]; // 距離標號計數

void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}

void add(int u, int v, int c, int rc=0) {
    edge[tot] = Edge(head[u], v, c);
    head[u] = tot++;
    edge[tot] = Edge(head[v], u, rc);
    head[v] = tot++;
}

int get_flow(int u, int flow) {
    if (u == T || flow == 0) return flow;
    int res = 0, f;
    for (int i = head[u]; ~i; i = edge[i].next) {
        int &v = edge[i].to;
        if (d[u] == d[v] + 1 && (f = get_flow(v, min(flow, edge[i].cap))) > 0) {
            edge[i].cap -= f;
            edge[i^1].cap += f;
            res += f;
            flow -= f;
            if (flow == 0) return res;
        }
    }
    if (!--gap[d[u]]) d[S] = cnt + 1; // Gap 優化
    gap[++d[u]]++;
    return res;
}

int isap() {
    int flow = 0;
    memset(gap, 0, sizeof(gap));
    memset(d, 0, sizeof(d));
    cnt = T - S + 1;
    gap[0] = cnt;
    while (d[S] < cnt) flow += get_flow(S, inf);
    return flow;
}

int main() {
    // 讀入圖的點數、邊數及點權，構建網絡後調用 isap() 即可得到答案
    // 具體輸入格式請參考 SPOJ 1476 題目描述
    return 0;
}

關鍵點總結

• 閉合子圖約束通過無窮大容量邊強制體現；
• ISAP 算法結合 Gap 優化與距離標號，工程上表現優異；
• 注意長整型防溢出，邊數上限需根據題目約束預留足夠空間。