最大流：Dinic模板

/*
Date : 2015-8-21 晚上

Author : ITAK

Motto :

今日的我要超越昨日的我，明日的我要胜过今日的我；
以创作出更好的代码为目标，不断地超越自己。
*/
#include <iostream>
#include <cstdio>

using namespace std;
///oo表示无穷大
const int oo = 1e9+5;
///mm表示边的最大数量，因为要双向建边
const int mm = 111111;
///点的最大数量
const int mn = 1000;
///node:节点数,src:源点,dest:汇点,edge:边数
int node, src, dest, edge;
///ver:边指向的结点,flow:边的流量,next:链表的下一条边
int ver[mm], flow[mm], next[mm];
///head:节点的链表头,work:用于算法中的临时链表头,dis:距离
int head[mn], work[mn], dis[mn], q[mn];

///初始化
void Init(int _node, int _src, int _dest)
{
    node = _node, src = _src, dest = _dest;
    for(int i=0; i<node; i++)
        head[i] = -1;
    edge = 0;
}

///增加边
void addedge(int u, int v, int c)
{
    ver[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
    ver[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}

///广搜计算出每个点与源点的最短距离，如果不能到达汇点说明算法结束
bool Dinic_bfs()
{
    int i, u, v, l, r = 0;
    for(i=0; i<node; i++)
        dis[i] = -1;
    dis[q[r++]=src] = 0;
    for(l=0; l<r; l++)
        for(i=head[u=q[l]]; i>=0; i=next[i])
            if(flow[i] && dis[v=ver[i]]<0)
            {
                ///这条边必须有剩余流量
                dis[q[r++]=v] = dis[u] + 1;
                if(v == dest)
                    return 1;
            }
    return 0;
}

///寻找可行流的增广路算法，按节点的距离来找，加快速度
int Dinic_dfs(int u, int exp)
{
    if(u == dest)
        return exp;
    ///work 是临时链表头，这里用 i 引用它，这样寻找过的边不再寻找*
    for(int &i=work[u],v,tmp; i>=0; i=next[i])
    {
        if(flow[i]&&dis[v=ver[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            ///正反向边容量改变
            flow[i] -= tmp;
            flow[i^1] += tmp;
            return tmp;
        }
    }

    return 0;
}

///求最大流，直到没有可行流
int Dinic_flow()
{
    int i, ret=0, data;
    while(Dinic_bfs())
    {
        for(i=0; i<node; i++)
            work[i] = head[i];
        while(data = Dinic_dfs(src, oo))
            ret += data;//cout<<666<<endl;
    }

    return ret;
}