题意:从起点到终点有几条特殊路径。
特殊路径指的是:对于任意两条路径,他们的与起点相连的点是不同的点 && 与终点的相连的点是不同的点。
/*
题意:从起点到终点有几条特殊路径。
特殊路径指的是:对于任意两条路径,他们的与起点相连的点是不同的点 && 与终点的相连的点是不同的点。
思路:
把起点和后继节点的流量设置为1,同理对终点处理
这样在寻找最大流的增广路径时就会消除一条。。
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<queue>
#include<iostream>
using namespace std;
const int maxn = ;
const int maxm = maxn*maxn;
const int inf = 0x3f3f3f3f;
struct Edge{
int u,v,next,val;
}edge[ maxm ];
int cnt,head[ maxn ];
int q[ maxn+ ];
int lev[ maxn+ ]; void init(){
cnt = ;
memset( head,-,sizeof( head ) );
}
void addedge( int a,int b,int c ){
edge[ cnt ].u = a;
edge[ cnt ].v = b;
edge[ cnt ].val = c;
edge[ cnt ].next = head[ a ];
head[ a ] = cnt ++;
} bool bfs( int src,int dest,int n ){
int head2 = ,tail2 = ;
q[ tail2++ ] = src;
memset( lev,-,sizeof( lev ) );
lev[ src ] = ;
while( head2<tail2 ){
int cur = q[ head2++ ];
for( int i=head[ cur ];i!=-;i=edge[ i ].next ){
int nxt = edge[ i ].v;
if( edge[ i ].val> && lev[ nxt ]==- ){
lev[ nxt ] = lev[ cur ] + ;
q[ tail2++ ] = nxt;
}
}
}
if( lev[ dest ]==- ) return false;
else return true;
} int Dinic( int src,int dest,int n ){
int maxFlow = ;
while( true ){
if( bfs( src,dest,n )==false )
break;
//printf("ok\n");
int id = src;
int tail = ;
while( true ){
if( id==dest ){
int flow = inf;
int flag = -;
for( int i=;i<tail;i++ ){
if( edge[ q[ i ] ].val<flow ){
flow = edge[ q[ i ] ].val ;
flag = i;
}
}
for( int i=;i<tail;i++ ){
edge[ q[ i ] ].val -= flow;
edge[ q[ i ]^ ].val += flow;
}
if( flag==- ) {
// printf("Un_Normal\n");
return inf;
}
else{
maxFlow += flow;
tail = flag;
id = edge[ q[ flag ] ].u;
}
}
//solve maxFlow
id = head[ id ];
while( id!=- ){
if( edge[ id ].val> && lev[ edge[id].u ]+==lev[ edge[id].v ] ){
break;
}
id = edge[ id ].next;
}
if( id!=- ){
q[ tail++ ] = id;
id = edge[ id ].v;
}
else{
if( tail== ) break;
lev[ edge[ q[ tail- ] ].v ] = -;
id = edge[ q[ --tail ] ].u;
}
}
}
//printf("Normal:\n");
return maxFlow;
} int main(){
//freopen( "in.txt","r",stdin );
int n;
//printf("ok\n");
while( scanf("%d",&n)== ){
init();
int cc;
int u,v;
//printf("begin input\n");
for( int i=;i<n;i++ ){
scanf("%d",&cc);
//printf("cc = %d\n",cc);
u = i;
while( cc-- ){
scanf("%d",&v);
if( u==||v==n ){
addedge( u,v, );
addedge( v,u, );
}
else{
addedge( u,v,inf );
addedge( v,u, );
}
}
}
int src = ;
int dest = n;
//printf("begin\n");
printf("%d\n",Dinic( src,dest,n ));
}
return ;
}