右图中标出了每条有向公路上最大的流量,请问从S点到T点最大的流量是________。
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <limits.h> #define min(a, b) ((a) < (b) ? (a) : (b)) int graph[7][7] = { {0, 28, 7, 0, 19, 0, 0 }, {0, 0, 6, 15, 0, 0, 0 }, {0, 0, 0, 0, 12, 0, 0 }, {0, 0, 0, 0, 0, 7, 23}, {0, 7, 0, 14, 0, 0, 36}, {0, 0, 10, 0, 0, 18, 0 }, {0, 0, 0, 0, 0, 0, 0 } }; #define vnum 7 const int vs = 0, vt = 6; int parent[vnum]; int visited[vnum]; int queue[vnum]; void bfs(int s) { int v; for(v = 0; v < vnum; v++) { visited[v] = 0; parent[v] = v; } int qhead = 0, qtail = 0; queue[qtail++] = s; visited[s] = 1; while(qtail != qhead) { int u = queue[qhead++]; for(v = 0; v < vnum; v++) { if(!visited[v] && graph[u][v]) { visited[v] = 1; parent[v] = u; queue[qtail++] = v; } } } } int main(void) { int sum = 0; while(1) { bfs(vs); int flow = INT_MAX; int t = vt; while(parent[t] != t) { int p = parent[t]; flow = min(flow, graph[p][t]); t = p; } if(t != vs || flow == 0) break; t = vt; while(parent[t] != t) { int p = parent[t]; graph[p][t] -= flow; graph[t][p] += flow; t = p; } sum += flow; } printf("%d\n", sum); return 0; }答案是46