您的位置: 首页  >  IT文章  >  luogu3376 【模板】 网络最大流 题目大意 概念 求最大流：Dinic算法

luogu3376 【模板】 网络最大流 题目大意 概念 求最大流：Dinic算法

分类: IT文章 • 2024-04-03 09:55:55

给出一个网络图，以及其源点和汇点，求出其网络最大流。

概念

可以把网络图看作管道，节点看作管道的交界处。流就像是管道里的流水。管道有个容量（相当于横截面积），还会有个流量（相当于水流占了管道的多少横截面积）。管道的交界处的流量满足流入的流量和等于流出的流量和。网络图有源点和汇点，水流必须从源流到汇。现在要你求整个图中的最大流（也就是从源点流出的流量的最大值）。

增广路径

在当前水流流动的情况下，对于一个从源点到汇点的路径，如果组成该路径的边都没有满流，则该路径便是一个增广路径。

显然，当前图的水流流动的情况下不存在增广路径当且仅当当前图中的总流量为图的最大流。

求最大流：Dinic算法

总体思路

不断地将流量尽量大的水流注入管道，直到网络图中没有增广路径为止。

具体过程

图中每条边存储的是当前边的剩余容量。对以下操作循环：首先从源点Bfs，对当前的可增广路径进行搜索，设置每一个节点的Level。节点的Level表示水流在网络图中流经的节点的顺序。随后Dfs，根据Bfs所得的Level的顺序向当前可增广路径中注入流量尽可能大的水流。

此处有个问题，处理当前可增广路径后的水流状态不一定就是最大流的水流状态呀！所以我们还要对每一条边设置一条反向边，以达到给机会后悔的目的，其初值为0。Dfs求出当前节点的下一个节点用去的水流nextTake后，当前边剩余容量-=nextTake，其反向边的容量+=nextTake。

最后，当Bfs后，如果汇点的Level没有设置上，意味着不存在增广路径了，此时输出结果：每次循环所得的汇点流出的流量之和。

优化

对于每一个节点我们可以设置一个DfsFrom，每次Dfs时，从DfsFrom开始遍历。具体步骤看代码。注意Dfs中for括号里和循环后对DfsFrom的处理。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX_NODE = 10010, MAX_EDGE = 100010 * 2, INF=0x3f3f3f3f;
#define LOOP(i, n) for(int i=1; i<=n; i++)

struct Dinic
{
private:
	struct Node;
	struct Edge;

	struct Node
	{
		int Level, Id;
		Edge *Head, *DfsFrom;
	}_nodes[MAX_NODE], *Start, *Target;
	int _vCount;

	struct Edge
	{
		Node *From, *To;
		Edge *Next, *Rev;
		int Cap;
	}*_edges[MAX_EDGE];
	int _eCount;

	Edge *NewEdge()
	{
		return _edges[++_eCount] = new Edge();
	}

	Edge *AddEdge(Node *from, Node *to, int cap)
	{
		Edge *e = NewEdge();
		e->From = from;
		e->To = to;
		e->Cap = cap;
		e->Next = from->Head;
		from->Head = e;
		return e;
	}

	bool Bfs()
	{
		LOOP(i, _vCount)
			_nodes[i].Level = 0;
		Start->Level = 1;
		static queue<Node*> q;
		q.push(Start);
		while (!q.empty())
		{
			Node *cur = q.front();
			q.pop();
			for (Edge *e = cur->Head; e; e = e->Next)
			{
				if (!e->To->Level && e->Cap)
				{
					e->To->Level = cur->Level + 1;
					q.push(e->To);
				}
			}
		}
		return Target->Level;
	}

	int Dfs(Node *cur, int limit)
	{
		if (cur == Target)
			return limit;
		if (limit == 0)
			return 0;
		int curTake = 0;
		for (Edge *e = cur->DfsFrom; e; e = cur->DfsFrom = e->Next)
		{
			if (e->Cap && e->To->Level == cur->Level + 1)
			{
				int nextTake = Dfs(e->To, min(limit - curTake, e->Cap));//易忘点：-curTake
				e->Cap -= nextTake;
				e->Rev->Cap += nextTake;
				curTake += nextTake;
			}
			if (limit - curTake == 0)//易忘点
				break;
		}
		return curTake;
	}

public:
	void Build(int uId, int vId, int cap)
	{
		Node *u = _nodes + uId, *v = _nodes + vId;
		u->Id = uId;
		v->Id = vId;
		Edge *e1 = AddEdge(u, v, cap), *e2 = AddEdge(v, u, 0);
		e1->Rev = e2;
		e2->Rev = e1;
	}

	int Proceed()
	{
		int ans = 0;
		while (Bfs())
		{
			LOOP(i, _vCount)
				_nodes[i].DfsFrom = _nodes[i].Head;
			ans += Dfs(Start, INF);
		}
		return ans;
	}

	Dinic() {}

	Dinic(int totNode, int sId, int tId):_vCount(totNode),Start(_nodes+sId),Target(_nodes+tId)
	{
		memset(_nodes, 0, sizeof(_nodes));
		memset(_edges, 0, sizeof(_edges));
	}

};

int main()
{
	//g.Test();
#ifdef _DEBUG
	freopen("c:\noi\source\input.txt", "r", stdin);
#endif
	int m, vCount, sId, tId;
	scanf("%d%d%d%d", &vCount, &m, &sId, &tId);
	static Dinic g(vCount, sId, tId);
	int uId, vId, cap;
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &uId, &vId, &cap);
		g.Build(uId, vId, cap);
	}
	int ans;
	ans = g.Proceed();
	printf("%d
", ans);
}

　　

相关推荐