CF103E Buying Sets 题解

· · 题解

我们把权值取反然后求最大权闭合子图，

题目给了条件，任意 k(k>0) 个集合的并集，包含的不同数字不会少于 k 个。

即对于任意左部点集合 S , |N(S)|\ge|S|，我们给每个数字赋上 -lim 的权值，给每个集合赋上 +lim(lim<<=+\infty) 的权值，发现选择的 -lim 的数量一定 \ge 选择的 +lim 的数量，所以当我们跑最大流的时候一定会选择数量相等的情况（这样流量最大）。

因为求的是最大权闭合子图，所以把源点 S 连向集合（正权值的点），容量为 lim+(-v_i)，数字（负权值的点）连向汇点 T，容量为 lim，集合连向集合内的数字，容量 +\infty。

最后答案和 0 取 \min 即可（即选择空集）。

附上代码：

#include<bits/stdc++.h>
#define FL(i,a,b) for(ll i=(a);i<=(b);i++)
#define FR(i,a,b) for(ll i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const ll MAXN = 6e2 + 10;
const ll MR = 1e5 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll lim = 1e18;
ll n,sum,S,T;
struct edge{
    ll v,w,nxt;
}e[MR<<1];
ll head[MAXN],now[MAXN],cnt=1;
ll dis[MAXN];
void Add_edge(ll u,ll v,ll w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt; 
}
bool bfs(){
    queue<ll>q;
    FL(i,0,(n<<1)+1) dis[i]=inf;
    dis[S]=0,now[S]=head[S];
    q.push(S);
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        for(ll i=head[u];i;i=e[i].nxt){
            ll v=e[i].v;
            if(e[i].w&&dis[v]==inf){
                dis[v]=dis[u]+1;
                now[v]=head[v];
                q.push(v);
                if(v==T) return 1; 
            }
        }
    }
    return 0;
}
ll dfs(ll u,ll flow){
    if(u==T) return flow;
    ll res=0;
    for(ll i=now[u];i&&flow;i=e[i].nxt){
        ll v=e[i].v;
        now[u]=i;
        if(e[i].w&&(dis[v]==dis[u]+1)){
            ll tmp=dfs(v,min(flow,e[i].w));
            if(!tmp) dis[v]=inf;
            e[i].w-=tmp;
            e[i^1].w+=tmp;
            res+=tmp,flow-=tmp;
        }
    }
    return res;
}
ll dinic(){
    while(bfs()) sum-=dfs(S,inf);
    return min(-sum,0ll);
}
signed main(){
    scanf("%lld",&n),S=0,T=(n<<1)+1;
    FL(i,1,n){
        ll x,y;
        scanf("%lld",&x);
        FL(j,1,x){
            scanf("%lld",&y);
            Add_edge(i,y+n,inf),Add_edge(y+n,i,0);
        }
    }
    FL(i,1,n){
        ll x;
        scanf("%lld",&x),sum+=lim-x;
        Add_edge(S,i,lim-x),Add_edge(i,S,0);
    }
    FL(i,1,n) Add_edge(i+n,T,lim),Add_edge(T,i+n,0);
    printf("%lld\n",dinic());
}