Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma comment(linker, "/STACK:16777216")
- #include<stdio.h>
- #include<string.h>
- #include<math.h>
- #include<stdlib.h>
- #include<ctype.h>
- #include<iostream>
- #include<vector>
- #include<stack>
- #include<queue>
- #include<set>
- #include<map>
- #include<string>
- #include<utility>
- #include<algorithm>
- #include<list>
- using namespace std;
- #define CLR(a) memset(a,0,sizeof(a))
- #define SET(a) memset(a,-1,sizeof(a))
- #define pb push_back
- #define SZ(a) ((long)a.size())
- #define ALL(a) a.begin(),a.end()
- #define FOREACH(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
- #define AREA2(x1,y1,x2,y2,x3,y3) ( x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2) )
- #define SQR(x) ((x)*(x))
- #define STR string
- #define IT iterator
- #define ff first
- #define ss second
- #define MP make_pair
- #define EPS 1e-9
- #define INF 1000000007
- #define chk(a,k) ((bool)(a&(1<<(k))))
- #define set0(a,k) (a&(~(1<<(k))))
- #define set1(a,k) (a|(1<<(k)))
- typedef long long Long;
- typedef vector<long> Vl;
- typedef vector<Long> VL;
- typedef pair<long,long> Pll;
- typedef pair<Long,Long> PLL;
- inline long FastMax(long x, long y) { return (((y-x)>>(32-1))&(x^y))^y; }
- inline long FastMin(long x, long y) { return (((y-x)>>(32-1))&(x^y))^x; }
- long IR[] = { 0,-1,0,1,-1,-1,1,1 };
- long IC[] = { 1,0,-1,0,1,-1,-1,1 };
- #define MAX_V 407
- #define MAX_E MAX_V*MAX_V
- struct EDGE{
- long v,c,f;
- };
- long nV;
- long SRC,TNK;
- long eI;
- EDGE Edge[MAX_E+7]; // edge list
- long Next[MAX_E+7]; // next pointer of vertex v
- long Last[MAX_V+7]; // last index of adj edge of vertex v
- long Dist[MAX_V+7]; // level from src
- long Start[MAX_V+7];// temporary used for last
- long N,st,tt;
- vector<Pll> List;
- inline void SetEdge( long u,long v,long c,long f )
- {
- Edge[eI].v = v;
- Edge[eI].c = c;
- Edge[eI].f = f;
- Next[eI] = Last[u];
- Last[u] = eI++;
- Edge[eI].v = u;
- Edge[eI].c = 0;
- Edge[eI].f = 0;
- Next[eI] = Last[v];
- Last[v] = eI++;
- }
- long Q[MAX_V+7];
- long Frnt,End;
- bool Bfs( void )
- {
- Frnt = End = 0;
- Q[End++] = SRC;
- long i;
- for( i=0;i<nV;i++){
- Dist[i] = INF;
- }
- Dist[SRC] = 0;
- long u,v;
- while( Frnt<End ){
- u = Q[Frnt++];
- for( i=Last[u];i!=-1;i=Next[i]){
- v = Edge[i].v;
- if( !Edge[i].c || Dist[v]<INF ) continue;
- Dist[v] = Dist[u] + 1;
- Q[End++] = v;
- }
- }
- return Dist[TNK] < INF;;
- }
- #define MIN( a,b ) a<b ? a:b
- long AugmentPath( long u,long f )
- {
- if( u==TNK ) return f;
- long Tot = 0;
- for( long &i = Start[u];i!=-1;i=Next[i] ){
- long v = Edge[i].v;
- if( !Edge[i].c ) continue;
- if( Dist[v] != Dist[u]+1 ) continue;
- long Tmp = AugmentPath( v,MIN( f,Edge[i].c ));
- Edge[i].c -= Tmp;
- Edge[i].f += Tmp;
- Edge[i ^ 1].c += Tmp;
- Edge[i ^ 1].f -= Tmp;
- Tot += Tmp;
- f -= Tmp;
- if( !f ) break;
- }
- return Tot;
- }
- long MaxFlow( void )
- {
- long Flw = 0;
- while( Bfs()){
- memcpy( Start,Last,(nV)*sizeof(long));
- Flw += AugmentPath( SRC,2*INF );
- }
- return Flw;
- }
- bool IsPos( long Lim )
- {
- st = N+1;
- tt = N+2;
- SRC = 0;
- TNK = N+2+1;
- nV = TNK+1;
- eI = 0;
- memset( Last,-1,nV*sizeof(long));
- long i,j;
- for( i=1;i<=N;i++ ){
- SetEdge( st,i,INF,0 );
- SetEdge( i,tt,INF,0 );
- }
- SetEdge( SRC,st,Lim,0 );
- SetEdge( tt,TNK,Lim,0 );
- long Flw = Lim;
- for( i=0;i<List.size();i++ ){
- SetEdge( List[i].ff,List[i].ss,INF,1 );
- SetEdge( List[i].ff,TNK,1,0 );
- SetEdge( SRC,List[i].ss,1,0 );
- Flw++;
- }
- //printf("%ld %ld\n",MaxFlow(),Flw );
- return MaxFlow()==Flw;
- }
- void FindPath( long st,long tt,vector<long> &Path )
- {
- if( st==tt ) return;
- Path.pb( st );
- for( long &i = Start[st];i!=-1;i=Next[i] ){
- if( Edge[i].f<=0 ) continue;
- if( Edge[i].v==SRC || Edge[i].v==TNK ) continue;
- Edge[i].f--;
- FindPath( Edge[i].v,tt,Path );
- break;
- }
- }
- int main( void )
- {
- long i,j,d,v,Icase,k = 0;
- //freopen("text1.txt","r",stdin );
- while( cin>>N ){
- List.clear();
- for( i=1;i<=N;i++ ){
- cin>>d;
- while( d-- ){
- cin>>v;
- List.pb( MP( i,v ) );
- }
- }
- long lo = 0,hi = List.size();;
- while( lo<hi ){
- long mi = (lo+hi)/2;
- if( IsPos( mi ) ) hi = mi;
- else lo = mi+1;
- }
- long Ans = hi;
- IsPos( Ans );
- printf("%ld\n",Ans );
- memcpy( Start,Last,(nV)*sizeof(long));
- for( i=1;i<=Ans;i++ ){
- vector<long> Path;
- FindPath( st,tt,Path );
- for( j=1;j<Path.size();j++ ){
- if( j>1 ) printf(" ");
- printf("%ld",Path[j] );
- }
- printf("\n");
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement