103E - Buying Sets - CodeForces Solution

#include<bits/stdc++.h>
#define pb push_back
#define MP make_pair
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll;
template<typename T>void readmain(T &x){
    bool neg=false;unsigned int c=getchar();
    for(;(c^48)>9;c=getchar())if(c=='-')neg=true;
    for(x=0;(c^48)<10;c=getchar())x=(x<<3)+(x<<1)+(c^48);
    if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
constexpr int N=605,M=130005;
constexpr ll inf=1e9;
int n,m,s,t,MAXN;
namespace MAXFLOW{
	int edgenum=1,head[N],cur[N],Next[M*2],vet[M*2],dis[N];
	ll flw[M*2],INF=1e18;
	queue<int> q;
	void add(int u,int v,ll w){
		edgenum++;
		Next[edgenum]=head[u];
		vet[edgenum]=v;
		flw[edgenum]=w;
		head[u]=edgenum;
	}
	void ADD(int u,int v,ll w){add(u,v,w);add(v,u,0);}
	bool bfs(int s,int t){
		for(int i=1;i<=MAXN;i++)cur[i]=head[i],dis[i]=-1;
		while(!q.empty())q.pop();
		q.push(s);dis[s]=1;
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int e=head[u];e;e=Next[e]){
				int v=vet[e];
				if(flw[e]>0&&dis[v]==-1){
					dis[v]=dis[u]+1;
					if(v==t)return 1;
					q.push(v);
				}
			}
		}
		return 0;
	}
	ll dfs(int u,int t,ll flow){
		if(!flow||u==t)return flow;
		ll used=0;
		for(int e=cur[u];e;e=Next[e]){
			int v=vet[e];cur[u]=e;
			if(dis[v]==dis[u]+1){
				ll tmp=dfs(v,t,min(flow-used,flw[e]));
				if(tmp==0)continue;
				flw[e]-=tmp;flw[e^1]+=tmp;
				used+=tmp;
				if(flow==used)break;
			}
		}
		return used;
	}
	ll dinic(int s,int t){ll FLOW=0;while(bfs(s,t))FLOW+=dfs(s,t,INF);return FLOW;}
}
using MAXFLOW::ADD,MAXFLOW::dinic;
ll ans;
int main(){
    read(n);
    s=n+n+1,t=s+1,MAXN=t;
    for(int i=1;i<=n;i++){
        int x;read(x);
        for(int j=1;j<=x;j++){
            int y;read(y);
            ADD(i,y+n,inf);
        }
    }
    for(int i=1;i<=n;i++){
        int x;read(x);ans+=x;
        ADD(s,i,inf-x);
        ADD(i+n,t,inf);
    }
    printf("%lld\n",ans-((ll)inf*n-dinic(s,t)));
    return 0;
}