C++ 基于Dijkstra最短路搜索的Ford Fulkson最大流算法

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cstring>

using namespace std;

const int MAXN = 120;
const int INF = INT_MAX;

int G[MAXN][MAXN], N;

int dist[MAXN], Pre[MAXN];
bool visited[MAXN];

int times = 0;

bool Dijkstra(int src, int dest) {
	for (int i = 0; i < N; ++i) {
		dist[i] = INF;
	}
	for (int i = 0; i < N; ++i) {
		Pre[i] = -1;
	}

	for (int i = 0; i < N; ++i) {
		visited[i] = false;
	}

	dist[src] = 0;

	for (int i = 0; i < N - 1; ++i) {
		//extract min
		int nd = -1;
		for (int i = 0; i < N; ++i) {
			if (!visited[i] && (nd == -1 || dist[i] < dist[nd]))
				nd = i;
		}
		if (dist[nd] == INF) 
			break;
		visited[nd] = true;

		//relax.
		for (int i = 0; i < N; ++i) {
			if (!visited[i] && G[nd][i] > 0 && dist[i] > dist[nd] + G[nd][i]) {
				dist[i] = dist[nd] + G[nd][i];
				Pre[i] = nd;
			}
		}
	}
	
	/*
	cout << (++times) << ": ";
	int e = dest;
	cout << dest << " ";
	while (Pre[e] != -1) {
		cout << Pre[e] << " ";
		e = Pre[e];
	}
	cout << endl;
	*/

	if (dist[dest] != INF)
		return true;
	else
		return false;
}

int Mx_flow(int src, int dest) {
	int ans = 0;

	while (Dijkstra(src, dest)) {
		int min_f = INF;

		//find min_f.
		int e = dest;
		while (Pre[e] != -1) {
			if (G[Pre[e]][e] < min_f)
				min_f = G[Pre[e]][e];
			e = Pre[e];
		}

		//cout << "minf: " << min_f << endl;

		//undate residual network
		e = dest;
		while (Pre[e] != -1) {
			G[Pre[e]][e] -= min_f;
			G[e][Pre[e]] += min_f;
			e = Pre[e];
		}

		//accumulate mx_flow.
		ans += min_f;
	}

	return ans;
}

int main(void) {
	memset(G, 0, sizeof(G));

	cin >> N;

	int m;
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int s, t, c;
		cin >> s >> t >> c;
		G[s][t] = c;
	}

	int mx_f = 0;
	int src, dest;
	cin >> src >> dest;

	clock_t  t = clock();
	mx_f = Mx_flow(src, dest);
	cout << "Time: " << (clock() - t) << "(ms)" << endl;
	cout << "Max_flow: " << mx_f << endl;

	system("pause");
	return 0;
}

C++ 基于Dijkstra最短路搜索的Ford Fulkson最大流算法

原文：http://blog.csdn.net/qq_21555605/article/details/46571893