网络最大流量算法

[eiclpy]

#include <cstdio>
const int MAX_NODE = 110, MAX_EDGE = 10010 * 2, INF = 1e9;
typedef int arrayN[MAX_NODE];
typedef int arrayE[MAX_EDGE];
int min(int a, int b) { return a < b ? a : b; }
arrayE edgeCost, edgeFlow, toNode, nextEdge;
arrayN cur, num, dis, pre, queue, head;
int n, qhead, tail;
void addEdge(int u, int v, int w)
{
	static int tot = 1;
	edgeCost[++tot] = w;
	edgeFlow[tot] = 0;
	toNode[tot] = v;
	nextEdge[tot] = head[u];
	head[u] = tot;
}
int ar(int s, int t) //确认流
{
	int flow = INF, p;
	for (p = t; p != s; p = toNode[pre[p] ^ 1])
		flow = min(flow, edgeCost[pre[p]] - edgeFlow[pre[p]]);
	for (p = t; p != s; p = toNode[pre[p] ^ 1])
		edgeFlow[pre[p]] += flow, edgeFlow[pre[p] ^ 1] -= flow;
	return flow;
}
void bfs(int s) //拓扑
{
	int now, p;
	queue[tail++] = s;
	dis[s] = 0;
	while (qhead < tail)
	{
		now = queue[qhead++];
		for (p = head[now]; p; p = nextEdge[p])
			if (toNode[p] != s && !dis[toNode[p]])
				dis[toNode[p]] = dis[now] + 1, queue[tail++] = toNode[p];
	}
}
int MAXflow(int s, int t)
{
	bool ok;
	int ans = 0, x = s, m, p, i;
	bfs(t); //对网络进行拓扑
	for (i = 1; i <= n; i++)
		num[dis[i]]++;
	for (i = 1; i <= n; i++)
		cur[i] = head[i];
	while (dis[s] < n)
	{
		ok = false;
		if (x == t) //到达目的地，更新流信息
			ans += ar(s, t), x = s;
		for (p = cur[x]; p; p = nextEdge[p])
			if (edgeCost[p] > edgeFlow[p] && dis[x] == dis[toNode[p]] + 1)
			{
				ok = true, cur[x] = p, pre[toNode[p]] = p, x = toNode[p];
				break;
			}
		if (!ok) //不可以流则回退
		{
			m = n;
			for (p = head[x]; p; p = nextEdge[p])
				if (edgeCost[p] > edgeFlow[p])
					m = min(m, dis[toNode[p]]);
			if (--num[dis[x]] == 0)
				break;
			num[dis[x] = m + 1]++;
			cur[x] = head[x];
			if (x != s)
				x = toNode[pre[x] ^ 1];
		}
	}
	return ans;
}

int main()
{
	int m, u, v, w;
	scanf("%d %d", &n, &m); //n节点，m边
	for (int i = 0; i < m; ++i)
	{
		scanf("%d %d %d", &u, &v, &w); //u，v间有可以通过w流量的边
		addEdge(u, v, w);			   //正向边流量w
		addEdge(v, u, 0);			   //空的反向边
		addEdge(v, u, w);
		addEdge(u, v, 0);
	}
	printf("Max flow from Node 1 to Node n:%d", MAXflow(1, n));
	return 0;
}