Алгоритм Форда-Фалкерсона: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 6: Строка 6:
  struct Edge {
  struct Edge {
     int a, b, cap, flow;
     int a, b, cap, flow;
     Edge(int a, int b, int cap) : a(a), b(b), cap(cap), flow(0) {}
     Edge(int a, int b, int cap, int flow) : a(a), b(b), cap(cap), flow(flow) {}
  };
  };
  vector<Edge> edges;
  vector<Edge> edges;
Строка 36: Строка 36:
     for (int i = 0; i < m; i++) {
     for (int i = 0; i < m; i++) {
         scanf("%d%d%d", &a, &b, &cap);
         scanf("%d%d%d", &a, &b, &cap);
         edges.push_back(Edge(a - 1, b - 1, cap));
         edges.push_back(Edge(a - 1, b - 1, cap, 0));
         g[a - 1].push_back(edges.size() - 1);
         g[a - 1].push_back(edges.size() - 1);
         edges.push_back(Edge(b - 1, a - 1, cap));
         edges.push_back(Edge(b - 1, a - 1, cap, cap));
         g[b - 1].push_back(edges.size() - 1);
         g[b - 1].push_back(edges.size() - 1);
     }
     }

Версия от 22:16, 23 мая 2015

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

struct Edge {
    int a, b, cap, flow;
    Edge(int a, int b, int cap, int flow) : a(a), b(b), cap(cap), flow(flow) {}
};
vector<Edge> edges;

int n, m, u[1010], INF = 1 << 30;
vector<int> g[1010];

int findPath(int v, int bottleneckFlow) {
    u[v] = 1;
    if (v == n - 1)
        return bottleneckFlow;
    for (int i = 0; i < g[v].size(); i++) {
       Edge &e = edges[g[v][i]], &re = edges[g[v][i] ^ 1];
       if (!u[e.b] && e.cap > e.flow) {
           int deltaFlow = findPath(e.b, min(bottleneckFlow, e.cap - e.flow));
           if (deltaFlow) {
               e.flow += deltaFlow;
               re.flow -= deltaFlow;
               return deltaFlow;
           }
       }
    }
    return 0;
}

int main() {
    scanf("%d%d", &n, &m);
    int a, b, cap;
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &cap);
        edges.push_back(Edge(a - 1, b - 1, cap, 0));
        g[a - 1].push_back(edges.size() - 1);
        edges.push_back(Edge(b - 1, a - 1, cap, cap));
        g[b - 1].push_back(edges.size() - 1);
    }
    
    int flow = 0;
    while (1) {
        fill(u, u + n, 0);
        int deltaFlow = findPath(0, INF);
        if (!deltaFlow)
            break;
        flow += deltaFlow;
    }
    printf("%d", flow);
}

Ссылки