SyntaxHighlighter

Thursday 19 June 2014

Поиск максимального потока в неориентированном графе


int N, Source, Dest;
vector<vi> C;
vi Use;

void addEdge(int u, int v, int w) {
    C[u][v] += w;
    C[v][u] += w;
}

int augment(int u, int val) {
    if (u == Dest) return val;
    Use[u] = true;
    for (int v = 0; v < N; ++v) {
        if (Use[v]) continue;
        if (C[u][v] <= 0) continue;
        int r = augment(v, min(val, C[u][v]));
        if (r > 0) {
            C[u][v] -= r;
            C[v][u] +=r;
            return r;
        }
    }
    return 0;
}

int maxFlow() {
    int flow = 0;
    Use = vi(N, 0);
    while (true) {
        fill(all(Use), false);
        int f = augment(Source, 1 << 30);
        if (f == 0) break;
        flow += f;
    }
    return flow;
}

No comments:

Post a Comment