题目链接

题目大意

有一个大小为 $n$ 的全集，每个元素是一个数，有$n$个子集，题目保证任意$k$个子集的并的大小$\geq k$。你需要选出一些子集使得这些子集的并大小等于子集个数，且其并中元素和最小，可以为空集。$n \leq 300$

题解

这个题有两种做法。

做法 1

如果不考虑限制条件 权值取反之后就是一个最大权闭合子图模型（选了集合就要选对应的元素）
考虑条件 “任意$k$个子集的并的大小$\geq k$” 如何用：这实际上保证了无论如何选择 元素个数$\geq$集合个数
于是我们把元素的权值$-\infty$，集合的权值 $+\infty$ 在最优化的限制下只有当相等的时候才会被采纳为答案（赋极端值法，这种有保证一个大于另一个的 要求相等都可以这样赋一个极端值）。
然后跑一个最大权闭合子图就好了。

#define int LL
const int MAXN = 1e5 + 5;

namespace Flow{
    struct Edge{
        int to,w,nxt;
    }e[MAXN<<1];
    int head[MAXN],cur[MAXN],cnt=1;
    int dep[MAXN];
    int S,T,N;

    inline void add(int u,int v,int w){
        e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
        e[++cnt] = (Edge){u,0,head[v]};head[v] = cnt;
    }

    inline bool bfs(){
        FOR(i,0,N) cur[i] = head[i],dep[i] = 0;
        std::queue<int> q;q.push(S);dep[S] = 1;
        while(!q.empty()){
            int v = q.front();q.pop();
            for(int i = head[v];i;i = e[i].nxt){
                if(e[i].w > 0 && !dep[e[i].to]){
                    dep[e[i].to] = dep[v] + 1;
                    if(e[i].to == T) return true;
                    q.push(e[i].to);
                }
            }
        }
        return dep[T];
    }

    inline int dfs(int v,int flow=1e9){
        if(v == T) return flow;
        if(!flow) return 0;
        int ans = 0;
        for(int &i = cur[v];i;i = e[i].nxt){
            if(e[i].w > 0 && dep[e[i].to] == dep[v] + 1){
                int t = dfs(e[i].to,std::min(flow,e[i].w));
                if(t>0){
                    ans += t;flow -= t;
                    e[i].w -= t;e[i^1].w += t;
                    if(!flow) break;
                }
            }
        }
        return ans;
    }

    inline int Dinic(){
        int ans = 0,t = 0;
        while(bfs()) while((t=dfs(S))) ans += t;
        return ans;
    }
};
using namespace Flow;
std::vector<int> to[MAXN];
int a[MAXN];
int n;

signed main(){
    scanf("%lld",&n);
    FOR(i,1,n){
        int sz;scanf("%lld",&sz);
        while(sz--){int x;scanf("%lld",&x);to[i].pb(x);}
    }
    FOR(i,1,n) scanf("%lld",a+i),a[i] = -a[i];
    int ans = 0;N = 2*n;S = ++N;T = ++N;
    FOR(i,1,n){
        for(auto x:to[i]) add(i,n+x,1e12);
        a[i] += 1e9;
        if(a[i] > 0) ans += a[i],add(S,i,a[i]);
        else add(i,T,-a[i]);
        add(i+n,T,1e9);
    }
    ans -= Dinic();
    printf("%lld\n",-ans);
    return 0;
}

做法 2

这个更像是有理有据的做法
根据条件我们不难想到对每个集合和每个元素都建一个点 组成一个二分图。每个集合向它包含的元素连边。发现这个图一定是存在完备匹配的。
我们设一组合法的方案所选取的两边的点集分别为 $X,Y$，取 $x \in X$。那么对于一个点 $x$ 它关联的所有的点都一定在 $Y$ 中。
我们接下来证明任意一组方案都可以被任意一个匹配表示。
方案 $\to$ 匹配：$x$ 一定有出边 并且对应点都在 $Y$ 中，一定存在一种方法给 $X$ 中每个点都分配一个点，其余的随便分配即可。
匹配 $\to$ 方案：$x$ 所有的对应点都在 $Y$ 中 所以匹配点一定在 $Y$ 中。
于是我们可以求一组匹配 用匹配构造解。现在相当于选了 $y \in Y$ 就必须选择 $y$ 的匹配点 就必须选择 $y$ 的匹配点的关联点。最大权闭合子图模型。
代码就咕了。