[bzoj2502]清理雪道[上下界网络流]

bzoj状态里有两种，一种时间是个位数，一种是四位数，我就是四位数的那种，，，估计都是看了hzwer..

 #include <bits/stdc++.h>

 #define    INF    0x3f3f3f3f

 using namespace std;

 template<const int _n,const int _m>

 struct Edge

 {

     struct Edge_base { int    to,next,w; }e[_m]; int    cnt,p[_n];

     Edge() { clear(); }

     void insert(const int x,const int y,const int z)

     { e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; }

     int    start(const int x) { return p[x]; }

     void    clear() { cnt=;memset(p,,sizeof(p)); }

     void    Link(const int x,const int y,const int z)

     { insert(x,y,z); insert(y,x,); }

     Edge_base&    operator[](const int x) { return e[x]; }

 };

 Edge<,>e;

 int    n,cnt,Flow,level[];

 int    SS,SSS,TTT,cur[],In[];

 bool    Bfs(const int S)

 {

     int    i,t;

     queue<int>    Q;

     memset(level,,sizeof(level));

     level[S]=;

     Q.push(S);

     while(!Q.empty())

     {

         t=Q.front();Q.pop();

         for(i=e.start(t);i;i=e[i].next)

         {

             if(!level[e[i].to] && e[i].w)

             {

                 level[e[i].to]=level[t]+;

                 Q.push(e[i].to);

             }

         }

     }

     return level[TTT];

 }

 int    Dfs(const int S,const int bk)

 {

     if(S==TTT)return bk;

     int    rest=bk;

     for(int &i=cur[S];i;i=e[i].next)

     {

         if(level[e[i].to]==level[S]+ && e[i].w)

         {

             int flow=Dfs(e[i].to,min(e[i].w,rest));

             e[i].w-=flow;

             e[i^].w+=flow;

             if((rest-=flow)<=)break;

         }

     }

     if(bk==rest)level[S]=;

     return bk-rest;

 }

 void    Dinic()

 {

     while(Bfs(SSS))

     {

         memcpy(cur,e.p,sizeof(cur));

         Flow+=Dfs(SSS,INF);

     }

     return ;

 }

 int main()

 {

     int    i,j,t,y;

     scanf("%d",&n);

     for(i=;i<=n;++i)

     {

         scanf("%d",&t);

         for(j=;j<=t;++j)

         {

             scanf("%d",&y);

             cnt++;

             e.Link(i,n+(cnt<<)-,INF);

             e.Link(n+(cnt<<),y,INF);

         }

     }

     SS=n+cnt+cnt+,SSS=SS+,TTT=SSS+;

     for(i=;i<=cnt;++i)

         e.Link(n+i+i-,n+i+i,INF),In[n+i+i-]--,In[n+i+i]++;

     for(i=n+;i<=n+cnt+cnt;++i)

         if(In[i]>)e.Link(SSS,i,In[i]);

         else    e.Link(i,TTT,-In[i]);

     for(i=;i<=n;++i)e.Link(SS,i,INF);

     i=;

     while(Flow!=cnt)

     {

         e.Link(SSS,SS,);

         Dinic();i++;

     }

     printf("%d\n",i);

     return ;

 }