(http://acmore.net/problem.php?id=1509) Edmonds-Karp

p1507.cpp

#include <cstdio>
#include <cstring>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>

const int M = 200;

int a[M], b[M], c[M];

const int V = M * 2 + 2;

int capacity[V][V], back[V];

int solve(int source, int target, int n) {
    int ret = 0;
    while (true) {
        memset(back, -1, sizeof(back));
        std::queue <int> queue;
        queue.push(source);
        while (!queue.empty()) {
            int u = queue.front();
            queue.pop();
            for (int v = 0; v < n; ++ v) {
                if (capacity[u][v] > 0 && back[v] == -1) {
                    back[v] = u;
                    queue.push(v);
                }
            }
        }
        if (back[target] == -1) {
            break;
        }
        int delta = INT_MAX;
        for (int v = target; v != source; v = back[v]) {
            delta = std::min(delta, capacity[back[v]][v]);
        }
        ret += delta;
        for (int v = target; v != source; v = back[v]) {
            capacity[back[v]][v] -= delta;
            capacity[v][back[v]] += delta;
        }
    }
    return ret;
}

int main() {
    int source, target;
    while (scanf("%d%d", &source, &target) == 2) {
        std::vector <int> values;
        values.push_back(source);
        values.push_back(target);
        int m;
        scanf("%d", &m);
        for (int i = 0; i < m; ++ i) {
            scanf("%d%d%d", a + i, b + i, c + i);
            values.push_back(a[i]);
            values.push_back(b[i]);
        }
        std::sort(values.begin(), values.end());
        values.erase(std::unique(values.begin(), values.end()), values.end());
#define FIND(v) (std::lower_bound(values.begin(), values.end(), v) - values.begin())
        memset(capacity, 0, sizeof(capacity));
        for (int i = 0; i < m; ++ i) {
            capacity[FIND(a[i])][FIND(b[i])] += c[i];
        }
        printf("%d\n", solve(FIND(source), FIND(target), (int)values.size()));
#undef FIND
    }
    return 0;
}

赞一个！