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;
}