//网络流SAP模板，复杂度O（N^2*M）

//使用前调用init（源点，汇点，图中点的个数），然后调用add_edge()加边

//调用getflow得出最大流

#define N 55

#define M 500500

#define INF 0x3fffff

struct Max_Flow

{

    struct node

    {

        int to,w,next;

    }edge[M];

    int s,t;

    int nn;

    int cnt,pre[N];

    int lv[N],gap[N];

    void init(int ss,int tt,int num)

    {

        s=ss;

        t=tt;

        nn = num;//

        cnt=;

        memset(pre,-,sizeof(pre));

    }

    void add_edge(int u,int v,int w)//同时建两条边

    {

        edge[cnt].to=v;

        edge[cnt].w=w;

        edge[cnt].next=pre[u];

        pre[u]=cnt++;

        edge[cnt].to=u;

        edge[cnt].w=;

        edge[cnt].next=pre[v];

        pre[v]=cnt++;

    }

    int sdfs(int k,int w)

    {

        if(k==t) return w;

        int f=;

        int mi=nn-;

        for(int p=pre[k];p!=-;p=edge[p].next)

        {

            int v=edge[p].to,tw=edge[p].w;

            if(tw!=)

            {

                if(lv[k]==lv[v]+)

                {

                    int tmp=sdfs(v,min(tw,w-f));

                    f+=tmp;

                    edge[p].w-=tmp;

                    edge[p^].w+=tmp;

                    if(f==w||lv[s]==nn) break;

                }

                if(lv[v]<mi) mi=lv[v];

            }

        }

        if(f==)

        {

            gap[lv[k]]--;

            if( gap[ lv[k] ]== )

            {

                lv[s]=nn;

            }

            lv[k]=mi+;

            gap[lv[k]]++;

        }

        return f;

    }

    int getflow()

    {

        int sum=;

        memset(lv,,sizeof(lv));

        memset(gap,,sizeof(gap));

        gap[]=nn;

        while(lv[s]<nn)

        {

            sum+=sdfs(s,INF);

        }

        return sum;

    }

};