Advertisement
LinKin

uva 1440

Oct 24th, 2013
153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.58 KB | None | 0 0
  1. #pragma comment(linker, "/STACK:16777216")
  2.  
  3. #include<stdio.h>
  4. #include<string.h>
  5. #include<math.h>
  6. #include<stdlib.h>
  7. #include<ctype.h>
  8. #include<iostream>
  9. #include<vector>
  10. #include<stack>
  11. #include<queue>
  12. #include<set>
  13. #include<map>
  14. #include<string>
  15. #include<utility>
  16. #include<algorithm>
  17. #include<list>
  18. using namespace std;
  19.  
  20. #define CLR(a) memset(a,0,sizeof(a))
  21. #define SET(a) memset(a,-1,sizeof(a))
  22. #define pb push_back
  23. #define SZ(a) ((long)a.size())
  24. #define ALL(a) a.begin(),a.end()
  25. #define FOREACH(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
  26. #define AREA2(x1,y1,x2,y2,x3,y3) ( x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2) )
  27. #define SQR(x) ((x)*(x))
  28. #define STR string
  29. #define IT iterator
  30. #define ff first
  31. #define ss second
  32. #define MP make_pair
  33. #define EPS 1e-9
  34. #define INF 1000000007
  35.  
  36. #define chk(a,k) ((bool)(a&(1<<(k))))
  37. #define set0(a,k) (a&(~(1<<(k))))
  38. #define set1(a,k) (a|(1<<(k)))
  39.  
  40. typedef long long Long;
  41. typedef vector<long> Vl;
  42. typedef vector<Long> VL;
  43. typedef pair<long,long> Pll;
  44. typedef pair<Long,Long> PLL;
  45.  
  46. inline long FastMax(long x, long y) { return (((y-x)>>(32-1))&(x^y))^y; }
  47. inline long FastMin(long x, long y) { return (((y-x)>>(32-1))&(x^y))^x; }
  48.  
  49. long IR[] = { 0,-1,0,1,-1,-1,1,1 };
  50. long IC[] = { 1,0,-1,0,1,-1,-1,1 };
  51.  
  52.  
  53. #define MAX_V 407
  54. #define MAX_E MAX_V*MAX_V
  55.  
  56. struct EDGE{
  57.     long v,c,f;
  58. };
  59. long nV;
  60. long SRC,TNK;
  61. long eI;
  62. EDGE Edge[MAX_E+7]; // edge list
  63. long Next[MAX_E+7]; // next pointer of vertex v
  64. long Last[MAX_V+7]; // last index of adj edge of vertex v
  65. long Dist[MAX_V+7]; // level from src
  66. long Start[MAX_V+7];// temporary used for last
  67.  
  68. long N,st,tt;
  69. vector<Pll> List;
  70.  
  71. inline void SetEdge( long u,long v,long c,long f )
  72. {
  73.     Edge[eI].v = v;
  74.     Edge[eI].c = c;
  75.     Edge[eI].f = f;
  76.     Next[eI] = Last[u];
  77.     Last[u] = eI++;
  78.     Edge[eI].v = u;
  79.     Edge[eI].c = 0;
  80.     Edge[eI].f = 0;
  81.     Next[eI] = Last[v];
  82.     Last[v] = eI++;
  83. }
  84.  
  85. long Q[MAX_V+7];
  86. long Frnt,End;
  87.  
  88. bool Bfs( void )
  89. {
  90.     Frnt = End = 0;
  91.     Q[End++] = SRC;
  92.     long i;
  93.     for( i=0;i<nV;i++){
  94.         Dist[i] = INF;
  95.     }
  96.     Dist[SRC] = 0;
  97.     long u,v;
  98.     while( Frnt<End ){
  99.         u = Q[Frnt++];
  100.         for( i=Last[u];i!=-1;i=Next[i]){
  101.             v = Edge[i].v;
  102.             if( !Edge[i].c || Dist[v]<INF ) continue;
  103.             Dist[v] = Dist[u] + 1;
  104.             Q[End++] = v;
  105.         }
  106.     }
  107.     return Dist[TNK] < INF;;
  108. }
  109.  
  110. #define MIN( a,b ) a<b ? a:b
  111.  
  112. long AugmentPath( long u,long f )
  113. {
  114.     if( u==TNK ) return f;
  115.     long Tot = 0;
  116.     for( long &i = Start[u];i!=-1;i=Next[i] ){
  117.         long v = Edge[i].v;
  118.         if( !Edge[i].c ) continue;
  119.         if( Dist[v] != Dist[u]+1 ) continue;
  120.         long Tmp = AugmentPath( v,MIN( f,Edge[i].c ));
  121.         Edge[i].c -= Tmp;
  122.         Edge[i].f += Tmp;
  123.         Edge[i ^ 1].c += Tmp;
  124.         Edge[i ^ 1].f -= Tmp;
  125.         Tot += Tmp;
  126.         f -= Tmp;
  127.         if( !f ) break;
  128.     }
  129.     return Tot;
  130. }
  131.  
  132. long MaxFlow( void )
  133. {
  134.     long Flw = 0;
  135.     while( Bfs()){
  136.         memcpy( Start,Last,(nV)*sizeof(long));
  137.         Flw += AugmentPath( SRC,2*INF );
  138.     }
  139.     return Flw;
  140. }
  141.  
  142. bool IsPos( long Lim )
  143. {
  144.     st = N+1;
  145.     tt = N+2;
  146.     SRC = 0;
  147.     TNK = N+2+1;
  148.     nV = TNK+1;
  149.     eI = 0;
  150.     memset( Last,-1,nV*sizeof(long));
  151.     long i,j;
  152.     for( i=1;i<=N;i++ ){
  153.         SetEdge( st,i,INF,0 );
  154.         SetEdge( i,tt,INF,0 );
  155.     }
  156.     SetEdge( SRC,st,Lim,0 );
  157.     SetEdge( tt,TNK,Lim,0 );
  158.     long Flw = Lim;
  159.     for( i=0;i<List.size();i++ ){
  160.         SetEdge( List[i].ff,List[i].ss,INF,1 );
  161.         SetEdge( List[i].ff,TNK,1,0 );
  162.         SetEdge( SRC,List[i].ss,1,0 );
  163.         Flw++;
  164.     }
  165.     //printf("%ld %ld\n",MaxFlow(),Flw );
  166.     return MaxFlow()==Flw;
  167. }
  168.  
  169.  
  170. void FindPath( long st,long tt,vector<long> &Path )
  171. {
  172.     if( st==tt ) return;
  173.     Path.pb( st );
  174.     for( long &i = Start[st];i!=-1;i=Next[i] ){
  175.         if( Edge[i].f<=0 ) continue;
  176.         if( Edge[i].v==SRC || Edge[i].v==TNK ) continue;
  177.         Edge[i].f--;
  178.         FindPath( Edge[i].v,tt,Path );
  179.         break;
  180.     }
  181. }
  182.  
  183. int main( void )
  184. {
  185.     long i,j,d,v,Icase,k = 0;
  186.  
  187.     //freopen("text1.txt","r",stdin );
  188.  
  189.     while( cin>>N ){
  190.         List.clear();
  191.         for( i=1;i<=N;i++ ){
  192.             cin>>d;
  193.             while( d-- ){
  194.                 cin>>v;
  195.                 List.pb( MP( i,v ) );
  196.             }
  197.         }
  198.         long lo = 0,hi = List.size();;
  199.         while( lo<hi ){
  200.             long mi = (lo+hi)/2;
  201.             if( IsPos( mi ) ) hi = mi;
  202.             else lo = mi+1;
  203.         }
  204.         long Ans = hi;
  205.         IsPos( Ans );
  206.         printf("%ld\n",Ans );
  207.         memcpy( Start,Last,(nV)*sizeof(long));
  208.         for( i=1;i<=Ans;i++ ){
  209.             vector<long> Path;
  210.             FindPath( st,tt,Path );
  211.             for( j=1;j<Path.size();j++ ){
  212.                 if( j>1 ) printf(" ");
  213.                 printf("%ld",Path[j] );
  214.             }
  215.             printf("\n");
  216.         }
  217.     }
  218.  
  219.     return 0;
  220. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement