#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 minint 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;elsereturn 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 networke = 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;}
，一错再错，把握正确的方向，
