HihoCoder1398：最大权闭合子图问题解析

在HihoCoder平台上的1398号问题中，我们面临的是一个经典的最大权闭合子图问题。该问题的核心在于从给定的图中找到一个子图，这个子图需要满足其内部的所有节点之间的边都在子图内部，同时这个子图的所有节点权重之和达到最大。

为了更好地理解这个问题，我们首先需要了解闭合子图的概念。简而言之，如果从图的一个子集中任选一点出发，沿着任何一条路径走，终点仍然在这个子集中，那么这个子集就是一个闭合子图。

最大权闭合子图是指，在一个赋予权重的图中，寻找一个闭合子图，使得这个子图中所有节点的权重总和最大。解决这一问题的关键在于构建一个网络流模型，并利用最大流算法来求解。

具体的步骤如下：

1. 构造一个超级源点S和一个超级汇点T，用于连接图中的其他节点。
2. 对于所有权重为正的节点，将其与超级源点S相连，边的容量设置为节点的权重值。
3. 对于所有权重为负的节点，将其与超级汇点T相连，边的容量设置为节点权重的绝对值。
4. 对于图中原有的边，保持不变，但将每条边的容量设为无穷大，以确保这些边不会成为瓶颈。
5. 计算从S到T的最大流（等价于最小割），最终的最大权闭合子图的权重即为所有正权重节点的权重总和减去最大流的值。

以下是解决此问题的C++代码示例：

#include 
#define N 100005
#define INF 0x7f7f7f7f
using namespace std;
int n, m, s, t, c, sum;
int head[N], cur[N], deep[N];
struct Edge {
    int to, next, w;
};
Edge e[2 * N];
void add(int x, int y, int z) {
    e[c].next = head[x]; e[c].w = z; e[c].to = y; head[x] = ++c;
}
bool bfs(int s, int t) {
    memset(deep, 0, sizeof(deep));
    deep[s] = 1;
    queue q;
    q.push(s);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = head[x]; i != -1; i = e[i].next) {
            int nex = e[i].to;
            if (!deep[nex] && e[i].w > 0) {
                deep[nex] = deep[x] + 1;
                q.push(nex);
            }
        }
    }
    return deep[t];
}
int dfs(int x, int t, int maxflow) {
    if (x == t) return maxflow;
    int ans = 0;
    for (int i = cur[x]; i != -1; i = e[i].next) {
        int nex = e[i].to;
        if (e[i].w <= 0 || ans >= maxflow || deep[nex] != deep[x] + 1) continue;
        cur[x] = i;
        int k = dfs(nex, t, min(e[i].w, maxflow - ans));
        e[i].w -= k;
        e[i ^ 1].w += k;
        ans += k;
    }
    if (ans == 0) deep[x] = -2;
    return ans;
}
int Dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
        memcpy(cur, head, sizeof(head));
        ans += dfs(s, t, INF);
    }
    return ans;
}
int main() {
    while (~scanf("%d%d", &n, &m)) {
        int x, y, z;
        s = 0;
        t = n + m + 1;
        c = 0;
        sum = 0;
        memset(head, -1, sizeof(head));
        for (int i = 1; i <= m; i++) {
            scanf("%d", &x);
            add(n + i, t, x);
            add(t, n + i, 0);
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &x, &y);
            sum += x;
            add(s, i, x);
            add(i, s, 0);
            for (int j = 1; j <= y; j++) {
                scanf("%d", &z);
                add(i, n + z, INF);
                add(n + z, i, 0);
            }
        }
        printf("%d\n", sum - Dinic(s, t));
    }
}