POJ 1273 - Drainage Ditches

http://poj.org/problem?id=1273

概要

N 本の排水路があり，M 個の交差点がある．1番目の交差点が池で，M 番目の交差点が川． i 番目の排水路は S[i] 番目の交差点から E[i] 番目の交差点へ最大で単位時間に C[i] の水を流す．

池から川へ単位時間に流れる最大の水量を答える．

制約

解法

最大流．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 #include <limits>
 5 using namespace std;
 6 
 7 template <typename T>
 8 T edmonds_karp(int N, vector<vector<T> > capacity, int source, int sink)
 9 {
10   vector<vector<T> > flow(N, vector<T>(N, 0));
11   T max_flow = 0;
12 
13   while (true) {
14     vector<int> parent(N, -1);
15     queue<int> q;
16     q.push(source);
17 
18     while (!q.empty() && parent[sink] < 0) {
19       const int v = q.front();
20       q.pop();
21 
22       for (int u = 0; u < N; u++) {
23         if (parent[u] < 0 && capacity[v][u] > 0) {
24           parent[u] = v;
25           if (u == sink) {
26             break;
27           }
28           q.push(u);
29         }
30       }
31     }
32 
33     if (parent[sink] < 0) {
34       break;
35     }
36 
37     T aug = numeric_limits<T>::max();
38     for (int v = sink; v != source; v = parent[v]) {
39       const int u = parent[v];
40       aug = min(aug, capacity[u][v]);
41     }
42     max_flow += aug;
43     for (int v = sink; v != source; v = parent[v]) {
44       const int u = parent[v];
45       flow[u][v] += aug;
46       flow[v][u] -= aug;
47       capacity[u][v] -= aug;
48       capacity[v][u] += aug;
49     }
50   }
51 
52   return max_flow;
53 }
54 
55 int main()
56 {
57   int N, M;
58   while (cin >> N >> M) {
59     vector<vector<long long> > cap(M, vector<long long>(M, 0));
60 
61     for (int i = 0; i < N; i++) {
62       int s, e, c;
63       cin >> s >> e >> c;
64       cap[s-1][e-1] += c;
65     }
66     cout << edmonds_karp(M, cap, 0, M-1) << endl;
67   }
68   return 0;
69 }
poj/1273.cc