最大流dinic总结模版

const int N=550;
const int M=300000;
const int inf=1<<30;
//******************************************//
struct Node
{
    int v,next;
    int val;
}edge[M];

int level[N];//顶点的层次
int head[N];
int que[N*100];//BFS中用于遍历的顶点，DFS求增广中记录边
int out[N];//DFS用于几乎定点的分支
int ind;

void init()
{
    ind=0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int c)
{
    edge[ind].v=v; edge[ind].val=c;  edge[ind].next=head[u];  head[u]=ind++;
    edge[ind].v=u; edge[ind].val=0;  edge[ind].next=head[v];  head[v]=ind++;
}
int dinic(int n,int source,int sink)
{
    int ret=0;
    int h=0,r=0;
    while(1)//DFS
    {
        int i;
        memset(level,0,sizeof(level));
        level[source]=1;
        que[h=r=0]=source;
        while(h<=r)//BFS
        {
            int  t=que[h++];
            for(i=head[t];i!=-1;i=edge[i].next)
                {
                    if(edge[i].val&&level[edge[i].v]==0)
                        {
                          level[edge[i].v]=level[t]+1;
                          que[++r]=edge[i].v;
                        }
                }
        }

        if(level[sink]==0)break;//找不到汇点
        for(i=0;i<=n;++i)out[i]=head[i];

        int  top=-1;
        while(1)
        {
            if(top<0)
            {
                int cur=out[source];
                for(;cur!=-1;cur=edge[cur].next)
                {
                    if(edge[cur].val&&out[edge[cur].v]!=-1&&level[edge[cur].v]==2)
                        break;
                }
                if(cur>=0)
                {
                    que[++top]=cur;
                    out[source]=edge[cur].next;
                }
                else
                    break;
            }
            int  u=edge[que[top]].v;
            if(u==sink)//一条增广路
            {
                int  dd=inf;
                int  index=-1;
                for(i=0;i<=top;i++)
                {
                    if(dd>edge[que[i]].val)
                    {
                        dd=edge[que[i]].val;
                        index=i;
                    }
                }
                ret+=dd;
                for(i=0;i<=top;i++)
                {
                    edge[que[i]].val-=dd;
                    edge[que[i]^1].val+=dd;
                }
                for(i=0;i<=top;i++)
                {
                    if(edge[que[i]].val==0)
                    {
                        top=index-1;
                          break;
                    }
                }
            }
            else
            {
                int cur=out[u];
                for(;cur!=-1;cur=edge[cur].next)
                {
                    if(edge[cur].val&&out[edge[cur].v]!=-1&&level[u]+1==level[edge[cur].v])
                        break;
                }
                if(cur!=-1)
                {
                    que[++top]=cur;
                    out[u]=edge[cur].next;
                }
                else
                {
                    out[u]=-1;
                    top--;
                }
            }
        }
    }
    return ret;
}
//**************************************************//