CF103E

有一点tricky的东西，不是很难。
做法1：用jzoj一道题的做法。
考虑最大权闭合子图对每个集合拆点(i)，每个元素拆点(i+n)。
则集合(i)选择，(S_i)的每个元素都要选择。
(i)的代价为(m_i)，(i+n)的代价为(0)
这是经典的最大权闭合子图，但是要求任意(i)个集合的并的元素个数必定是(i)，不太能做。
由于规定了任意(i)个集合的并的元素个数必定大于等于(i)，任意(i)个集合的并的元素个数-(igeq 0)
也就是说对于每个子集，任意(i)个集合的并的元素个数(-i)的最小值等于(0)（这很难想到）
于是可以修改上面的网络流模型，用(inf)限制任意(i)个集合的并的元素个数(-i)的最小值等于(0)。
设一个选择方案的代价为价值减去(inf*)限制任意(i)个集合的并的元素个数(-i)的最小值，则(inf*)限制任意(i)个集合的并的元素个数(-i)的最小值必须为(0)才最优。
于是修改成(i)的代价为(m_i+inf)，(i+n)的代价为(-inf)即可。
最小权只需要费用取反即可。
做法2：我在思考那道题时的一个想法。
这个做法本质和做法1相同。
可以用一个二元组表示选择方案的代价：((a,b))表示价值为(b)，集合的并的元素个数-(i)为(a)
比较时先比较(a)再比较(b)。
两个二元组((a,b)+(c,d))的加法定义为((a+c,b+d))
两个二元组的最小值定义为((a-c,b-d))（不能定义为((a-min(a,c),b-min(b,d)))）
设(i)的代价为((1,m_i))，(i+n)的代价为((-1,0))，把每条边的代价也设为二元组，最大流即可。

#include<bits/stdc++.h>
using namespace std;
#define N 400010
#define M 400010
#define int long long
int h[M],nxt[M],v[M],w[M],s,t,dep[M],ec,n,p[N],T,a[N],ans;
char st[N];
void add(int a,int b,int c){v[++ec]=b;w[ec]=c;nxt[ec]=h[a];h[a]=ec;}
void adj(int a,int b,int c){
	add(a,b,c);
	add(b,a,0);
}
int id(int x,int y){
	return (x-1)*n+y;
}
bool bfs(){
    queue<int>q;
	q.push(s);
    for(int i=1;i<=t;i++)
    	dep[i]=0;
	dep[s]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=h[x];i;i=nxt[i])
            if(w[i]&&!dep[v[i]]){
            	dep[v[i]]=dep[x]+1;
				q.push(v[i]);
            	if(v[i]==t)
					return 1;
			}
    }
	return 0;
}
int dfs(int x,int dis){
    if(x==t)
		return dis;
	int tp=dis;
    for(int i=h[x];i;i=nxt[i])
        if(dep[v[i]]==dep[x]+1&&w[i]){
            int f=dfs(v[i],min(tp,w[i]));
            if(!f)
				dep[v[i]]=0;
            tp-=f;
            w[i]-=f;
			w[i^1]+=f;
            if(!tp)
				break;
        }
    return dis-tp;
}
int din(){
    int aans=0;
    while(bfs()){
    	int v;
    	while(v=dfs(s,1e9))
			aans+=v;
	}
    return aans;
}
signed main(){
	ec=1;
	scanf("%lld",&n);
	int ans=0;
	t=n+n+1;
	for(int i=1;i<=n;i++){
		int c,x;
		scanf("%lld",&c);
		for(int j=1;j<=c;j++){
			scanf("%lld",&x);
			adj(x+n,i,1e13);
		}
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		adj(i,t,1e9-a[i]);
		ans+=1e9-a[i];
		adj(s,i+n,1e9);
	}
	printf("%lld
",din()-ans);
}