C++ 基于Dijkstra算法和基于BFS算法的Ford Fulkson算法比较

#include<iostream>#include<cstdlib>#include<cstdio>#include<ctime>#include<cstring>#include<vector>#include<queue>#include<array>#include<windows.h>using namespace std;const int INF = INT_MAX;//Edmond Karp.bool EK_bfs(vector<vector<int> > &G, int src, int dest, vector<int> &Pre) {vector<int> visited(G.size(), false);vector<int> _Pre(G.size(), -1);queue<int> Q;Q.push(src);visited[src] = true;while (!Q.empty()) {int nd = Q.front();if (nd == dest) break;Q.pop();for (int i = 0; i < G.size(); ++i) {if (!visited[i] && G[nd][i] > 0) {_Pre[i] = nd;Q.push(i);visited[i] = true;}}}Pre.swap(_Pre);if (Pre[dest] == -1) return false;else return true;}struct Node{int dist;bool visited;Node() : dist(INF), visited(false) {}};bool Dijkstra(vector<vector<int> > &G, int src, int dest, vector<int> & Pre) {vector<Node> D(G.size());vector<int> _Pre(G.size(), -1);D[src].dist = 0;for (int i = 0; i < G.size() – 1; ++i) {//extract minint min = -1;for (int j = 0; j < G.size(); ++j) {if (!D[j].visited && (min == -1 || D[j].dist < D[min].dist))min = j;}if (D[min].dist == INF) break;else D[min].visited = true;//relaxfor (int j = 0; j < G.size(); ++j) {if (!D[j].visited && G[min][j] > 0&& D[j].dist > D[min].dist + G[min][j]) {D[j].dist = D[min].dist + G[min][j];_Pre[j] = min;}}}Pre.swap(_Pre);if (D[dest].dist == INF) return false;else return true;}int Max_flow(vector<vector<int> > & G, int src, int dest) {int mxf = 0;vector<int> Pre;while (Dijkstra(G, src, dest, Pre)) {//while (EK_bfs(G, src, dest, Pre)) {int minf = INF;int e = dest;while (Pre[e] != -1) {minf = min(minf, G[Pre[e]][e]);e = Pre[e];}e = dest;while (Pre[e] != -1) {G[Pre[e]][e] -= minf;G[e][Pre[e]] += minf;e = Pre[e];}mxf += minf;}return mxf;}int main(void) {int N, M;while (cin >> N >> M) {vector<vector<int> > G(N, vector<int>(N, 0));for (int i = 0; i < M; ++i) {int s, t;cin >> s >> t;cin >> G[s][t];//G[s][t] > 0}int src, dest;cin >> src >> dest;int mx_f;LARGE_INTEGER t1, t2, tc;QueryPerformanceFrequency(&tc);QueryPerformanceCounter(&t1);mx_f = Max_flow(G, src, dest);QueryPerformanceCounter(&t2);printf("Use Time:%f\n", (t2.QuadPart – t1.QuadPart)*1.0 / tc.QuadPart);cout << "Max_flow: " << mx_f << endl;}system("pause");return 0;}输入样本:

680 1 20 2 31 3 31 4 12 3 12 4 13 5 24 5 30 5

样本输出:

Use Time:0.000168 (不同情况有不同结果)Max_flow: 4

，刺是与生俱来的，上帝在赐予优越感同时捆-绑的附属品;