P4843

思路大致是连出原图之后建立虚拟源汇点S,T，答案就是从S到T的有下界最小流

#include<bits/stdc++.h>
using namespace std;
const int N=1e4,M=1e5,inf=1e6;
int n,m,S,T,s,t;
int deg[N];
int h[N],e[M],ne[M],idx,f[M];
void add(int a,int b,int c){
	e[idx]=b,f[idx]=c,ne[idx]=h[a],h[a]=idx,idx++;
	e[idx]=a,f[idx]=0,ne[idx]=h[b],h[b]=idx,idx++;
}
int d[N],cur[N];
queue<int> q;
inline int read(){
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
bool bfs(){
	while(!q.empty())q.pop();
	memset(d,-1,sizeof d);
	q.push(s);d[s]=0,cur[s]=h[s];
	while(!q.empty()){
		int u=q.front();
//		cout<<u<<" ";
		q.pop();
		for(int i=h[u];~i;i=ne[i]){
			int v=e[i];
			if(d[v]==-1 && f[i]){
				d[v]=d[u]+1,cur[v]=h[v];
				if(v==t)return true;
				q.push(v);
			}
		}
	}
	return false;
}
int find(int u,int limit){
	if(u==t)return limit;
	int flow=0;
	for(int i=cur[u];~i && flow<limit;i=ne[i]){
		int v=e[i];
		cur[u]=i;
		if(d[v]-d[u]==1 && f[i]){
			int t=find(v,min(f[i],limit-flow));
			if(!t)d[v]=-1;
			else{
				flow+=t;
				f[i]-=t,f[i^1]+=t;
			}
		}
	}
	return flow;
}
int dinic(){
	int res=0,flow;
	while(bfs()){/*cout<<endl;*/while(flow=find(s,inf))res+=flow;}
	return res;
}
int main(){
	memset(h,-1,sizeof h);
	n=read();
	S=n+1,T=n+2;
	s=n+3,t=n+4;
	for(int i=1;i<=n;i++){
		int r=read();
		for(int j=0;j<r;j++){
			int v=read();
			add(i,v,inf);
			deg[i]-=1;
			deg[v]+=1;
		}
		add(S,i,inf);
		add(i,T,inf);
	}
	for(int i=1;i<=n+2;i++){
		if(deg[i]<0)add(s,i,-deg[i]);
		if(deg[i]>0)add(i,t,deg[i]);
	}
	int ext=dinic();
	s=T,t=S;
	cout<<ext-dinic()<<endl;
}