最大流Dinic算法

[micsama]

最大流Dinic算法

Dinic算法
（1）概述：Dinic算法的思路是这样的：每次都不停地用BFS来构造“层次图”，然后用“阻塞流”来增广。这里我特别标出了两个关键词——层次图，阻塞流。

什么是层次图呢？假设在残余网络中，起点到结点u的距离是dist(u)，那么dist(u)就是结点u的“层次”。只保留每个点出发到下一层次的弧，就得到了一张层次图。

什么是阻塞流呢？其实就是不考虑反向弧时的“极大流”，比如从s到t的层次图（注意此时是残量网络）中找到了一条简单路径是s->1->3->t。其中s->1的容量是10,1->3的容量是4，3->t的容量是10。那么极大流就是4（因为最大不能超过路径上所有容量的最小值）。4也就是阻塞流。可以直接理解为简单路径上的最小残量值。

因此，该算法第一次就是将上述那条简单路径的所有流量值加上4（这一过程叫“增广”），然后重复原来的过程直到s到t的简单路径不存在为止。可以证明，Dinic算法的时间复杂度的理论上界是O(N^2*M)（N是结点数，M是边数），但实际上Dinic算法比这个理论上界好得多。如果所有边容量均为1，那么时间复杂度是O(min(N^0.67,M^0.5)M)；对于二分图最大匹配这样的特殊图，时间复杂度是O(N^0.5M)。

struct Dinic
{
	static const int N = 510, M = 100010;
	int head[N];//链表头部，存储以u开始的边序号
	int en[M];//记录v
	int Next[M];//记录下一条边的序号
	int cap[M];//记录容量
	int tot;//边数
 
	void clear()
	{
		memset(head, 0, sizeof(head));
		tot = 1;
	}
	void add(int u, int v, int w)
	{
		en[++tot] = v;
		Next[tot] = head[u];
		head[u] = tot;
		cap[tot] = w;
	}
	void Add(int u, int v, int w){ add(u, v, w); add(v, u, 0); }
	int d[N], cur[N];
	int n, s, t;
	bool bfs()
	{
		queue<int>q;
		memset(d, -1, sizeof(d));
		d[s] = 0;
		q.push(s);
		while (!q.empty())
		{
			int x = q.front(); q.pop();
			for (int k = head[x],v; k; k = Next[k])
			if (cap[k] && d[v = en[k]]==-1)
			{
				d[v] = d[x] + 1;
				q.push(v);
			}
		}
		return d[t] != -1;
	}
	int dfs(int x, int y)
	{
		if (x == t || !y)return y;
		int z = y;
		for (int&k = cur[x],v; k; k = Next[k])
		if (cap[k] && d[v = en[k]] == d[x] + 1)
		{
			int w = dfs(v, min(cap[k], z));
			cap[k] -= w;//流量增大意味着净容量减少
			cap[k ^ 1] += w;//反向边容量表示了正向边的流量
			z -= w;
			if (!z)break;
		}
		if (z == y)d[x] = -1;
		return y - z;
	}
	int Maxflow(int s, int t)
	{
		this->s = s, this->t = t;
		int flow = 0;
		while (bfs())
		{
			for (int i = 1; i <= n; i++)
				cur[i] = head[i];
			flow += dfs(s, INF);
		}
		return flow;
	}
};