[模板] - 网络流 - Dinic

变量：

const int maxn = 207, INF = 0x3f3f3f3f;
int n, m;//n个点，m条边 
int mp[maxn][maxn]；//邻接矩阵
int que[maxn*maxn], head, tail;//BFS队列 ,首,尾
int dist[maxn];//距源点距离,分层图 
int ans;

函数：

BFS查询是否连通：

bool bfs() {
memset(dist,-1,sizeof dist);//dist一定要记得设置为-1
    dist[1] = head = 0;
    que[1] = tail = 1;
register int u,v;
while(head < tail) {
        u = que[++head];
for(v=1 ; v<=n ; v++) {
if(mp[u][v] > 0 && dist[v] < 0) {
                dist[v] = dist[u] + 1;
                que[++tail] = v;
            }
        }
    }
return dist[n] > 0;//汇点的DIS小于零,表明BFS不到汇点
}

递归寻找增广路并修改剩余流量：

//Find代表一次增广,函数返回本次增广的流量,返回0表示无法增广
int find(int from, int low) {//low变量始终不更新
//low是源点到现在最窄的(剩余流量最小)的边的剩余流量
if (from == n) return low;//当前点是汇点
for (int i = 1, tmp = 0; i <= n; i++)
if (mp[from][i] > 0//两点之间连通
            && dist[i] == dist[from] + 1//且当前点是分层图的下一层
            && bool(tmp = find(i, min(low, mp[from][i])))) {//且tmp!=0，说明可以和汇点连通
//上面if中更新的是tmp
            mp[from][i] -= tmp;
            mp[i][from] += tmp;
return tmp;//这里return的是tmp不是low
        }
return 0;
}

Dinic()：

int Dinic() {
int ans = 0;
while(bfs())
//要不停地建立分层图,如果BFS不到汇点才结束
while(tmp = find(1, INF), tmp != 0)
//每次BFS之后要不停地找增广路,直到找不到为止
            ans += tmp;
return ans;
}

注：

  网络流的最大流等于最小割。