Description

Input

Output

Sample Input

Sample Output

HINT

Source

【题解】带上下界最小流，具体可以看《妈妈我终于会了最小流系列》

http://blog.csdn.net/popoqqq/article/details/48467349

# include <stdio.h>
# include <string.h>
# include <queue>

using namespace std;

const int M=1000010;
int S,T,SS,TT,head[M],c[M],next[M],to[M],flow[M],w[M],tot=1;
int n;
queue<int> q;
// remember: tot starts from 1

inline void add(int u,int v,int fl) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	flow[tot]=fl;
}

inline void Add(int u,int v,int fl) {
	add(u,v,fl);
	add(v,u,0);
}

inline void qc() {
	while(!q.empty()) q.pop();
}

inline bool bfs() {
	qc(); memset(c,-1,sizeof(c));
	q.push(S);c[S]=1;
	while(!q.empty()) {
		int top=q.front(); q.pop();
		for (int i=head[top];i;i=next[i]) {
			int _to=to[i];
			if(c[_to]>=0 || flow[i]==0) continue;
			c[_to]=c[top]+1;
			q.push(_to);
			if(_to==T) return 1;
		}
	}
	return 0;
}

inline int dfs(int x,int low) {
	if(x==T) return low;
	int fl,r=low;
	for (int i=head[x];i;i=next[i]) {
		int _to=to[i];
		if(c[_to]!=c[x]+1 || flow[i]==0) continue;
		fl=dfs(_to,min(r,flow[i]));
		r-=fl;
		flow[i]-=fl;
		flow[i^1]+=fl;
		if(!r) return low;
	}
	if(r==low) c[x]=-1;
	return low-r;
}

inline int dinic() {
	int ans=0;
	while(bfs()) ans+=dfs(S,200011300); 
	return ans; 
}

int deg[M];


int main() {
	scanf("%d",&n);
	S=102,SS=103,T=104,TT=105;
	for (int i=1,t,tt;i<=n;++i) {
		scanf("%d",&t);
		for (int j=1;j<=t;++j) {
			scanf("%d",&tt);
			deg[i]--;
			deg[tt]++;
			Add(i,tt,200011300);
		}
	}
	for (int i=1;i<=n;++i) {
		if(deg[i]>0) Add(S,i,deg[i]);
		if(deg[i]<0) Add(i,T,-deg[i]);
		Add(SS,i,200011300);
		Add(i,TT,200011300);
	}
	Add(TT,SS,200011300);
	dinic();
	int ans1=0;
	for (int i=head[S];i;i=next[i])
		flow[i]=flow[i^1]=0;
	for (int i=head[T];i;i=next[i])
		flow[i]=flow[i^1]=0;
	for (int i=head[TT];i;i=next[i]) {
		if(to[i]==SS) {
			ans1+=flow[i^1];
			flow[i]=flow[i^1]=0;
			break;
		}
	}
	Add(S,TT,200011300);
	Add(SS,T,200011300);
	int ans2=dinic();
	printf("%d\n",ans1-ans2);
	return 0;
}