Максимальный поток минимальной стоимости: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: « #include <stdio.h> #include <algorithm> #include <vector> #include <queue> using namespace std; class Edge { int _a, _b, capacity, flow, cost; publi…»)
 
Нет описания правки
Строка 1: Строка 1:
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
  class Edge {
  class Edge {
     int _a, _b, capacity, flow, cost;
     int _a, _b, capacity, flow, cost;
Строка 33: Строка 27:
     vector<int> distTo;
     vector<int> distTo;
     vector<int> edgeTo;
     vector<int> edgeTo;
    static const int INF = 1 << 30;
     void fordBellman(int v) {
     void fordBellman(int v) {
         while (1) {
         while (1) {
Строка 38: Строка 33:
             for (int i = 0; i < edges.size(); i++) {
             for (int i = 0; i < edges.size(); i++) {
                 int a = edges[i].a(), b = edges[i].b();
                 int a = edges[i].a(), b = edges[i].b();
                 if (edges[i].capacityTo(b) && distTo[b] > distTo[a] + edges[i].costTo(b)) {
                 if (edges[i].capacityTo(b) && distTo[a] != INF && distTo[b] > distTo[a] + edges[i].costTo(b)) {
                     distTo[b] = distTo[a] + edges[i].costTo(b);
                     distTo[b] = distTo[a] + edges[i].costTo(b);
                     edgeTo[b] = i;
                     edgeTo[b] = i;
                     update = 1;
                     update = 1;
                 }
                 }
                 if (edges[i].capacityTo(a) && distTo[a] > distTo[b] + edges[i].costTo(a)) {
                 if (edges[i].capacityTo(a) && distTo[b] != INF && distTo[a] > distTo[b] + edges[i].costTo(a)) {
                     distTo[a] = distTo[b] + edges[i].costTo(a);
                     distTo[a] = distTo[b] + edges[i].costTo(a);
                     edgeTo[a] = i;
                     edgeTo[a] = i;
Строка 54: Строка 49:
     }
     }
     bool hasPath(int from, int to) {
     bool hasPath(int from, int to) {
         fill(distTo.begin(), distTo.end(), 1 << 30);
         fill(distTo.begin(), distTo.end(), INF);
         distTo[from] = 0;
         distTo[from] = 0;
         fordBellman(from);
         fordBellman(from);
         return distTo[to] != 1 << 30;
         return distTo[to] != INF;
     }
     }
     int bottleneckCapacity(int from, int to) {
     int bottleneckCapacity(int from, int to) {
         int bCapacity = 1 << 30;
         int bCapacity = INF;
         for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
         for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
             bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
             bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
Строка 91: Строка 86:
     }
     }
  };
  };
int main() {
    int n;
    scanf("%d", &n);
    Graph g(2 * n + 2);
    int source = 0;
    for (int i = 1; i <= n; i++)
        g.addEdge(source, i, 1, 0);
    int c;
    for (int i = 1; i <= n; i++) {
        for (int j = n + 1; j <= 2 * n; j++) {
            scanf("%d", &c);
            g.addEdge(i, j, 1, c);
        }
    }
    int sink = 2 * n + 1;
    for (int i = n + 1; i <= 2 * n; i++)
        g.addEdge(i, sink, 1, 0);
    printf("%lld", g.minCostMaxFlow(source, sink).first);
}


== Ссылки ==
== Ссылки ==

Версия от 01:47, 7 августа 2016

class Edge {
    int _a, _b, capacity, flow, cost;
public:
    Edge(int a, int b, int capacity, int cost) : _a(a), _b(b), capacity(capacity), flow(0), cost(cost) {}
    int a() const {
        return _a;
    }
    int b() const {
        return _b;
    }
    int other(int v) const {
        return v == _a ? _b : _a;
    }
    int capacityTo(int v) const {
        return v == _b ? capacity - flow : flow;
    }
    int costTo(int v) const {
        return v == _b ? cost : -cost;
    }
    void addFlowTo(int v, int f) {
        flow += (v == _b ? f : -f);
    }
};

class Graph {
    vector<Edge> edges;
    vector<int> distTo;
    vector<int> edgeTo;
    static const int INF = 1 << 30;
    void fordBellman(int v) {
        while (1) {
            bool update = 0;
            for (int i = 0; i < edges.size(); i++) {
                int a = edges[i].a(), b = edges[i].b();
                if (edges[i].capacityTo(b) && distTo[a] != INF && distTo[b] > distTo[a] + edges[i].costTo(b)) {
                    distTo[b] = distTo[a] + edges[i].costTo(b);
                    edgeTo[b] = i;
                    update = 1;
                }
                if (edges[i].capacityTo(a) && distTo[b] != INF && distTo[a] > distTo[b] + edges[i].costTo(a)) {
                    distTo[a] = distTo[b] + edges[i].costTo(a);
                    edgeTo[a] = i;
                    update = 1;
                }
            }
            if (!update)
                break;
        }
    }
    bool hasPath(int from, int to) {
        fill(distTo.begin(), distTo.end(), INF);
        distTo[from] = 0;
        fordBellman(from);
        return distTo[to] != INF;
    }
    int bottleneckCapacity(int from, int to) {
        int bCapacity = INF;
        for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
            bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
        return bCapacity;
    }
    long long addFlow(int from, int to, int flow) {
        long long deltaCost = 0;
        for (int v = to; v != from; v = edges[edgeTo[v]].other(v)) {
            edges[edgeTo[v]].addFlowTo(v, flow);
            deltaCost += flow * edges[edgeTo[v]].costTo(v);
        }
        return deltaCost;
    }
public:
    Graph(int verticesCount) {
        distTo.resize(verticesCount);
        edgeTo.resize(verticesCount);
    }
    void addEdge(int from, int to, int capacity, int cost) {
        edges.push_back(Edge(from, to, capacity, cost));
    }
    pair<long long, long long> minCostMaxFlow(int from, int to) {
        long long cost = 0, flow = 0;
        while (hasPath(from, to)) {
            int deltaFlow = bottleneckCapacity(from, to);
            cost += addFlow(from, to, deltaFlow);
            flow += deltaFlow;
        }
        return make_pair(cost, flow);
    }
};

Ссылки

Теория:

Код:

Задачи: