Description

滑雪场坐落在FJ省西北部的若干座山上。从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

求无源汇的网络流最小流。

首先构造源点S和汇点T，从源点向每个点连INF流量表示可以从每个点开始滑行无数次，从每个点向汇点连INF表示可以从每个点结束滑行无数次。原图中的边每条边流量下界为1，流量上界INF（可经过无数次），然后求满足条件的最小流。

构造超级源SS和超级汇TT，按照带流量下界的可行流做法，对于一条u->v流量上界为a且下界为b的边，连SS->v流量上限b，u->TT流量上限为b，u->v流量上限为a-b。原汇点T->S连一条流量上限为INF的边。

先跑一次网络流，T->S的边的流量记为x，然后拆掉超级源和超级汇以及T->S的边，将T作为原点、S作为汇点再跑一次网络流，答案记为y，则最小流为x-y。（对于本题必定有解，否则要判断所有上限为b的边是否满流，若不满流则无解）

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue> 
using namespace std;

#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
const int maxn=500, inf=0x3f3f3f3f;
typedef long long LL;
struct tyh{
	int f,t,flow,n;
};
tyh naive[maxn * maxn];
int head[maxn], top[maxn], nn=1;
int S, T, SS, TT, n;
queue<int> q;
bool chk[maxn];
int dep[maxn], ans;

void addedge(int f, int t, int flow)
{
	nn++;
	naive[nn].f=f;
	naive[nn].t=t;
	naive[nn].flow=flow;
	naive[nn].n=head[f];
	head[f]=nn;
}

void link(int f, int t, int flow)
{
	addedge(f,t,0);
	addedge(t,f,flow);
}

bool bfs()
{
	int nowp=SS;
	q.push(nowp);
	memset(dep,0,sizeof(dep));
	dep[nowp]=1;
	while (!q.empty())
	{
		nowp=q.front();
		q.pop();
		for (int e=head[nowp]; e; e=naive[e].n)
		{
//			printf("%d\n",naive[e^1].flow);
			if (naive[e^1].flow)
			{
				if (!dep[naive[e].t])
				{
					dep[naive[e].t]=dep[nowp]+1;
					q.push(naive[e].t);
				}
			}
		}
	}
	return dep[TT];
}

int dfs(int nowp, int flow)
{
	if (nowp==TT) return flow;
//	printf("%d %d[from %d to %d]\n",nowp,flow,SS,TT);
	int used=0;
	for (int &e=top[nowp]; e; e=naive[e].n)
	{
//		printf("%d--%d\n",dep[nowp],dep[naive[e].t]);
		if (naive[e^1].flow&&(dep[naive[e].t]==dep[nowp]+1))
		{
//			printf("==>%d\n",naive[e].t);
			int tmp1=dfs(naive[e].t,min(flow-used,naive[e^1].flow));
			used+=tmp1;
			naive[e].flow+=tmp1;
			naive[e^1].flow-=tmp1;
			if (used==flow)
				return used;
		}
	}
	if (!used)
		dep[nowp]=0;
	return used;
}

int dinic()
{
	int ans=0;
	while (bfs())
	{
		for (int i=1; i<=TT; i++)
			top[i]=head[i];
		ans+=dfs(SS,inf);
	}
	return ans;
}

void rebuild()
{
	for (int e=2; e<=nn; e++)
	{
		if (naive[e].f==SS||naive[e].t==SS||naive[e].f==TT||naive[e].t==TT)
			naive[e].flow=0; 
	}
	link(SS,T,inf);
	link(S,TT,inf);
}

int main()
{
	int num, to, cost;
	scanf("%d",&n);
	S=n+1;
	T=n+2;
	SS=n+3;
	TT=n+4;
	for (int i=1; i<=n; i++)
	{
		scanf("%d",&num);
		link(S,i,inf);
		link(i,T,inf);
		for (int j=1; j<=num; j++)
		{
			scanf("%d",&to);
			link(i,to,inf);
			link(SS,to,1);
		}
		if (num) link(i,TT,num);
	}
	link(T,S,inf);
//	for (int e=2; e<=nn; e+=2)
//		printf("%d==%d==>%d\n",naive[e].f,naive[e^1].flow,naive[e].t);
//	while(1);
	int TtoS=nn^1;
	dinic();
	int ans1=naive[TtoS].flow;
	
	naive[TtoS].flow = 0;
	naive[TtoS^1].flow = 0;
	rebuild();
	int ans2=dinic();
	printf("%d\n",ans1-ans2);
	return 0;
}