题解 CF103E 【Buying Sets】

· · 题解

提供一种更为巧妙的做法，不需要进行二分图匹配。

题意

有一个大小为 n 的全集，每个元素是一个数，有 n 个子集。题目保证任意 k 个子集的并的大小 \ge k 。
每个子集有一个可正可负的权值，你需要选出一些子集使得这些子集并的大小等于子集个数，且所选子集的权值和最小，可以为空集。

题解

把子集和元素分别看成两类物品，我们可以知道，如果我们选择了一个子集，那么我们必须选择所有属于它的元素。这启发我们往最大权闭合子图的方向转化。
我们先忽略“子集并的大小等于子集个数”这个条件，就是最小权闭合子图的经典模型，把每个子集的权值取反就可以做了。

那么，如何解决这一限制呢？
“任意 k 个子集的并的大小 \ge k ”是一个很强的性质，我们可以考虑从这里入手。
我们给每个元素赋上-\infty的权值，给每个子集赋上+\infty的权值，由上述条件，任意方案选择的子集数量都\le元素数量。所以所选择的-\infty的数量都\le选择的+\infty的数量。当且仅当方案满足限制时，所有赋上的权值会相互抵消。而最大流总是会寻找最优的方案，所以在有解的情况下，求出的答案一定合法，且所有附加权值都已消去。
而由于我们可以选择空集，所以一定存在合法的方案。

实现中有两个细节要注意：

  1. 最大权闭合子图建模的过程中，必须同时选择的物品间流量为+\infty的边的权值必须大于赋上的权值。在代码中，我用lim表示赋上的无穷大权值，用inf表示建图过程中的无穷大权值。
  2. 由于可以选择空集，输出时答案要和0取个\min。

代码

#include<bits/stdc++.h>
#define reg register
using namespace std;
typedef long long ll;
const int lim=3e8+5;
const int inf=0x3f3f3f3f;
const int V=605;
const int E=181205;
int to[E],nxt[E],c[E],h[V],cnt;
inline void ins(int s,int t,int w){
    to[cnt]=t;nxt[cnt]=h[s];c[cnt]=w;h[s]=cnt++;
    to[cnt]=s;nxt[cnt]=h[t];c[cnt]=0;h[t]=cnt++;
}
int S,T,level[V],iter[V],que[V];
bool bfs(){
    memset(level,-1,sizeof(level));
    reg int he=0,ta=1;que[0]=S;level[S]=1;
    while(he<ta){
        reg int v=que[he++];
        for(reg int i=h[v];~i;i=nxt[i]){
            if(c[i]&&level[to[i]]<0){
                level[to[i]]=level[v]+1;
                que[ta++]=to[i];
            }
        }
    }
    return level[T]>0;
}
int dfs(int st,int f){
    if(st==T)return f;
    reg int used=0,w;
    for(reg int& i=iter[st];~i;i=nxt[i])
        if(c[i]&&level[to[i]]==level[st]+1){
            w=dfs(to[i],min(c[i],f-used));
            if(!w)continue;
            c[i]-=w;c[i^1]+=w;used+=w;
            if(f==used)return f;
        }
    return used;
}
int n;
int main(){
    memset(h,-1,sizeof(h));
    scanf("%d",&n);T=n+n+1;
    for(reg int i=1,k,x;i<=n;i++){
        scanf("%d",&k);
        while(k--)scanf("%d",&x),ins(i,x+n,inf);
    }
    reg ll Ans=0,f;
    for(reg int i=1,x;i<=n;i++)
        scanf("%d",&x),ins(S,i,lim-x),Ans+=lim-x;
    for(reg int i=1;i<=n;i++)ins(i+n,T,lim);
    while(bfs()){
        memcpy(iter,h,sizeof(h));
        while(f=dfs(S,inf))Ans-=f;
    }
    printf("%lld\n",min(-Ans,0ll));
    return 0;
}