CF103E Buying Sets 题解

#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());
}