1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
|
#include <cstring> #include <queue> #define N 101 #define MIN(a, b) ((a) < (b) ? (a) : (b))
int () { int n, Case = 0; int adj[N][N] = {}; int path[N] = {};
while (scanf("%d", &n) && n) { int s, t, c, u, v, w; scanf("%d%d%d", &s, &t, &c); for (int i = 0; i < c; ++i) { scanf("%d%d%d", &u, &v, &w); adj[u][v] += w; adj[v][u] += w; }
int flow = 0;
while (true) { memset(path, 0, sizeof path);
std::queue<int> Q; Q.push(s); path[s] = s; while (!Q.empty() && !path[t]) { int now = Q.front(); Q.pop(); for (int i = 1; i <= n; ++i) if (!path[i] && adj[now][i] > 0) { path[i] = now; Q.push(i); } }
if (!path[t]) break;
int new_f = 1e9; for (int from = path[t], to = t; from != to; from = path[to = from]) { new_f = MIN(new_f, adj[from][to]); } for (int from = path[t], to = t; from != to; from = path[to = from]) { adj[from][to] -= new_f; adj[to][from] += new_f; } flow += new_f; }
printf("Network %dnThe bandwidth is %d.nn", ++Case, flow);
for (int i = 1; i <= n; ++i) memset(adj[i], 0, sizeof adj[i]); }
return 0; }
|
近期评论