最大流Dinic模板

///最大流Dinic模板
const int mx=1005;
struct Eage
{
    int u,v;
    int next,cap;
};
Eage eage[mx*2];
int head[mx];
int d[mx];
int pos;
int n,m;

void Init()
{
    memset(head,-1,sizeof(head));
    pos=0;
}

void add(int u,int v,int w)
{
    eage[pos].v=v;
    eage[pos].cap=w;
    eage[pos].next=head[u];
    head[u]=pos++;
}

int bfs()
{
    queue<int>q;
    memset(d,0,sizeof(d));
    d[1]=1;
    q.push(1);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=head[u];i!=-1;i=eage[i].next)
        {
            int v=eage[i].v;
            if (!d[v]&&eage[i].cap>0)
            {
                d[v]=d[u]+1;
                q.push(v);
            }
        }
    }
    return d[n];
}

int dfs(int u,int w)
{
    if (u==n||w==0) return w;
    int ans=0;
    for (int i=head[u];i!=-1;i=eage[i].next)
    {
        int v=eage[i].v;
        if (d[u]==d[v]-1&&eage[i].cap>0)
        {
            int temp=dfs(v,min(w,eage[i].cap));
            if (temp<=0) continue;
            eage[i].cap-=temp;
            eage[i^1].cap+=temp;
            w-=temp;
            ans+=temp; ///改成 return temp有时候会快很多。 
        }
    }
    return ans;
}

int dinic()
{
    int ans=0;
    while (bfs()) ans+=dfs(1,10000000);
    return ans;
}