CF103E Buying Sets 题解

题意：

有一个大小为 \(n~(1 \le n \le 300)\) 的全集，每个元素是一个数

现在有 \(n\) 个子集，大小分别为 \(m_i\) ，题目保证任意 \(k\) 个子集的并的大小 \(\ge k\) 。

每个子集有一个可正可负的权值，你需要选出一些子集使得这些子集并的大小等于子集个数，

且所选子集的权值和最小。可以为空集。保证 \(\sum m_i \le 10^6\) 。

输入格式：

第一行 \(n\) ，接下来 \(n\) 行：每行第一个数是 \(m_i\) ，接下来 \(m_i\) 个数是集合中的数。

最后一行 \(n\) 个数，表示每个子集

输出格式

一行，即权值和的最小值。

考虑将权值取反，这样只需要求最大权值。

注意到，如果我们将集合看作一些点，\(n\) 个数看作 \(n\) 个点，将集合与其中的点连边

那么，不考虑「子集并的大小等于子集个数」这个限制的话，这就是一个经典的最大权闭合子图问题。

最大权闭合子图问题，就是给定一张有向图，每个点有点权（可能为负）。

现在要找到一个点权和最大的子图，满足如果 \(u\) 在这个子图中，那么所有 \(u\) 的后继都在子图中。

这个问题可以用最小割解决。

对于点权 \(w_i > 0\) 的点，连边 \(S\to i\) ，容量为 \(w_i\) 。

对于点权 \(w_i < 0\) 的点，连边 \(i \to T\) ，容量为 \(-w_i\) （显然是正数）。

对于原图中的边 \(e \in E\) ，连边 \(e\) 即可，容量为 \(+\infty\) 。

那么答案就是所有正点权的权值之和 减去最小割。证明略。

现在考虑「子集并的大小等于子集个数」。

记 \(\mathrm{INF}\) 为一个极大值（正数），\(w_i\) 为取反后的集合的权值。

考虑以下最小割模型：

\(S\) 连向集合，容量为 \(\mathrm{INF} + w_i\) （割掉这条边相当于不选这个集合）。
集合连向集合内的元素，容量为 \(\rm INF\) 。
元素向 \(T\) 连边，容量为 \(\rm INF\) （割掉这条边相当于选这个元素）。

不难发现，在最小割方案中，割掉集合连向集合内的数字的边是不优的。

由于题目保证任意 \(k\) 个子集的并的大小 \(\ge k\) ，根据 Hall 定理（如下）

对于一个二分图 \(G\sim (X,Y)\) ，\(X\) 存在一个匹配的充分必要条件为：

对于 \(X\) 的任意子集 \(S\) ，\(S\) 的邻居的个数 \(|N(S)|\) 满足 \(|N(S)| \ge |S|\) 。

换句话说，左侧任选 \(i\) 个点，右侧都至少有 \(i\) 个点跟它对应。

即这个图是一定存在完美匹配的，且满足 \(|N(S)| \ge |S|\) ，所以至少会割掉 \(n\) 条边

又因为边权最少为 \(\mathrm{INF}\) ，所以不会选超过 \(n\) 条边，否则一定不优。

那么设最小割选了集合 \(S\) 包括的（表示元素的）点，那么有 \[ |S| = |N(S)| \] 时间复杂度 \(\mathcal{O}\left(|V|^2|E|\right)\) ，其中 \(|V| = \mathcal{O}(n),|E| = \mathcal{O}(n^2)\) 。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(666))
#define M ((int)(5e5 + 15))

int S, T, tot, pos = 1, head[N], now[N], dep[N];
struct Edge { int v, w, next; } e[M];
void addEdge(int u, int v, int w) { e[++pos] = {v, w, head[u]}; head[u] = pos; }
void add(int u, int v, int w) { addEdge(u, v, w); addEdge(v, u, 0); }
bool bfs()
{
    static queue<int> q; rep(i, 1, tot) dep[i] = INF;
    q.push(S); dep[S] = 1; now[S] = head[S];
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].v;
            if(e[i].w > 0 && dep[v] == INF)
            {
                dep[v] = dep[u] + 1;
                now[v] = head[v]; q.push(v);
            }
        }
    }
    return dep[T] != INF;
}
int dfs(int u, int in)
{
    if(u == T) return in;
    int out = 0;
    for(int i = now[u]; i; i = e[i].next)
    {
        if(!in) break; int v = e[i].v; now[u] = i;
        if(e[i].w > 0 && dep[v] == dep[u] + 1)
        {
            int res = dfs(v, min(in, e[i].w));
            e[i].w -= res; e[i ^ 1].w += res;
            in -= res; out += res;
        }
    }
    if(!out) dep[u] = INF;
    return out;
}
int Dinic()
{
    int res = 0;
    while(bfs()) res += dfs(S, INF);
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, x, res = 0; cin >> n; S = n * 2 + 1; T = S + 1; tot = T;
    rep(i, 1, n) { cin >> x; rep(j, 1, x){ cin >> x; add(i, x + n, INF); } }
    rep(i, 1, n) { cin >> x; res -= x; add(S, i, INF - x); add(i + n, T, INF); }
    res -= Dinic() - INF * n; cout << -res << '\n';
    return 0;
}