上下界网络流的做法大佬们都讲过了，我就来讲一个另类的解法。（不过也是网络流）
这个做法是考场上想了很久都不会后奇思妙想想出来的（不会上下界网络流），所以没多少思路引导。
首先原题明显可以转移成一个类似最小链覆盖的问题。
剩下的就是我的具体做法：
我们对原来的有向无环图进行改造：
上面的是原图，我们把图中的每一条边 e i e_i ei 拆成两条边：一条流量为 1 1 1，费用为 1 1 1，不妨取名叫 a i a_i ai；一条流量为 ∞ infty ∞，费用为 0 0 0，取名叫 b i b_i bi。然后源点向每个入度为 0 0 0 的点（也就是链覆盖的起点）连边，流量 ∞ infty ∞，费用 0 0 0；每个出度为 0 0 0 的点（也就是链覆盖的终点）向汇点连边，流量 ∞ infty ∞，费用 0 0 0。
然后跑最大费用最大流。
意思就是说每次增广时，相当于我新覆盖一条链。在增广中：
如果某条原图中的边 e i e_i ei 没有被走过，那么为了满足最大费用，程序肯定会选择流费用为 1 1 1 的那条边 a i a_i ai，费用增加 1 1 1，代表我新清理了一条雪道，即新访问了一条原图中的边；
如果这条边 e i e_i ei 被走过了，那么费用为 1 1 1 的那条边肯定被流满了，只能流费用为 0 0 0 的边，不贡献费用，意思就是我走过的这条边在我前几次覆盖时已经被覆盖了，也就是说我只是路过这，并不要清理这。
然后根据最大费用最大流的特性，每次增广完后，能保证所得的解是当前的最优解，也就是说它能保证用最优方法覆盖所有边。
那么当贡献的费用等于总边数时，整个图也就被我们覆盖完了，答案就是链的条数，也就是覆盖的次数，或者说增广的次数。
整道题也就结束了。
顺带说一下，其实这种跑网络流却不跑完，把网络流当成一个类似贪心的工具来使用的 trick 挺实用也挺常见的（类似数学中的设而不求），比如 BZOJ2893征服王 也可以用这个 trick 做，而且比这个麻烦一点，所以建议总结一下（
代码如下：
#include<bits/stdc++.h>
#define N 110
#define M 10010
#define INF 0x7fffffff
using namespace std;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
int n,s,t,tot,ans;
int rudu[N],chudu[N];
int cnt=1,head[N],to[N*4+M*4],nxt[N*4+M*4],c[N*4+M*4],w[N*4+M*4];
int pre[N],dis[N];
bool inq[N];
queue<int>q;
void adde(int u,int v,int ci,int wi)
{
to[++cnt]=v;
c[cnt]=ci;
w[cnt]=wi;
nxt[cnt]=head[u];
head[u]=cnt;
to[++cnt]=u;
c[cnt]=0;
w[cnt]=-wi;
nxt[cnt]=head[v];
head[v]=cnt;
}
bool SPFA()
{
memset(dis,128,sizeof(dis));
q.push(s);
dis[s]=0;
inq[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]&&dis[u]+w[i]>dis[v])
{
dis[v]=dis[u]+w[i];
pre[v]=i;
if(!inq[v])
{
inq[v]=1;
q.push(v);
}
}
}
}
return dis[t]!=dis[0];
}
void MCMF()
{
int maxcost=0,maxflow=0;
while(SPFA())
{
int minflow=INF;
for(int u=t;u!=s;u=to[pre[u]^1])
minflow=min(minflow,c[pre[u]]);
for(int u=t;u!=s;u=to[pre[u]^1])
{
c[pre[u]]-=minflow;
c[pre[u]^1]+=minflow;
maxcost+=minflow*w[pre[u]];
}
maxflow+=minflow;
ans++;//统计增广次数（链的条数）
if(maxcost==tot) break;//如果最大费用达到总边数
}
}
int main()
{
n=read();
s=1,t=1+n+1;
for(int i=1;i<=n;i++)
{
int m=read();
tot+=m;
for(int j=1;j<=m;j++)
{
int v=read();
adde(1+i,1+v,1,1);//ai
adde(1+i,1+v,INF,0);//bi
chudu[i]++,rudu[v]++;
}
}
for(int i=1;i<=n;i++)
{
if(!rudu[i]) adde(s,1+i,INF,0);//源点连入度为0的点
if(!chudu[i]) adde(1+i,t,INF,0);//出度为0的点连汇点
}
MCMF();//最大费用最大流
printf("%d
",ans);
return 0;
}
/*
5
1 2
0
2 2 4
0
1 4
*/