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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: « #include <stdio.h> #include <algorithm> #include <vector> #include <queue> using namespace std; class Edge { int _a, _b, capacity, flow, cost; publi…»)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
  #include <stdio.h>
  class Graph {
#include <algorithm>
    struct Edge {
#include <vector>
        int a, b, capacity, flow = 0, cost;
#include <queue>
using namespace std;
   
   
class Edge {
        Edge(int a, int b, int capacity, int cost) :
    int _a, _b, capacity, flow, cost;
            a(a), b(b), capacity(capacity), cost(cost) {}
public:
    Edge(int a, int b, int capacity, int cost) : _a(a), _b(b), capacity(capacity), flow(0), cost(cost) {}
         int other(int v) const {
    int a() const {
            return v == a ? b : a;
         return _a;
        }
    }
    int b() const {
        int capacityTo(int v) const {
        return _b;
            return v == b ? capacity - flow : flow;
    }
        }
    int other(int v) const {
        return v == _a ? _b : _a;
        int costTo(int v) const {
    }
            return v == b ? cost : -cost;
    int capacityTo(int v) const {
        }
        return v == _b ? capacity - flow : flow;
    }
        void addFlowTo(int v, int deltaFlow) {
    int costTo(int v) const {
            flow += (v == b ? deltaFlow : -deltaFlow);
        return v == _b ? cost : -cost;
        }
    }
    };
    void addFlowTo(int v, int f) {
        flow += (v == _b ? f : -f);
    }
};
   
   
class Graph {
     vector<Edge> edges;
     vector<Edge> edges;
     vector<int> distTo;
     vector<int> distTo;
     vector<int> edgeTo;
     vector<int> edgeTo;
     void fordBellman(int v) {
    static const int INF = 1e9;
     void fordBellman(int start) {
        fill(distTo.begin(), distTo.end(), INF);
        distTo[start] = 0;
         while (1) {
         while (1) {
             bool update = 0;
             bool update = 0;
             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;
Строка 53: Строка 50:
         }
         }
     }
     }
     bool hasPath(int from, int to) {
        fill(distTo.begin(), distTo.end(), 1 << 30);
     bool hasPath(int start, int finish) {
        distTo[from] = 0;
         fordBellman(start);
         fordBellman(from);
         return distTo[finish] != INF;
         return distTo[to] != 1 << 30;
     }
     }
     int bottleneckCapacity(int from, int to) {
         int bCapacity = 1 << 30;
     int bottleneckCapacity(int start, int finish) {
         for (int v = to; v != from; v = edges[edgeTo[v]].other(v))
         int bCapacity = INF;
         for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
             bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
             bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
         return bCapacity;
         return bCapacity;
     }
     }
     long long addFlow(int from, int to, int flow) {
     long long addFlow(int start, int finish, int deltaFlow) {
         long long deltaCost = 0;
         long long deltaCost = 0;
         for (int v = to; v != from; v = edges[edgeTo[v]].other(v)) {
         for (int v = finish; v != start; v = edges[edgeTo[v]].other(v)) {
             edges[edgeTo[v]].addFlowTo(v, flow);
             edges[edgeTo[v]].addFlowTo(v, deltaFlow);
             deltaCost += flow * edges[edgeTo[v]].costTo(v);
             deltaCost += deltaFlow * edges[edgeTo[v]].costTo(v);
         }
         }
         return deltaCost;
         return deltaCost;
     }
     }
  public:
  public:
     Graph(int verticesCount) {
     Graph(int vertexCount) :
         distTo.resize(verticesCount);
         distTo(vertexCount), edgeTo(vertexCount) {}
        edgeTo.resize(verticesCount);
      
     }
     void addEdge(int from, int to, int capacity, int cost) {
     void addEdge(int from, int to, int capacity, int cost) {
         edges.push_back(Edge(from, to, capacity, cost));
         edges.push_back(Edge(from, to, capacity, cost));
     }
     }
     pair<long long, long long> minCostMaxFlow(int from, int to) {
     pair<long long, long long> minCostMaxFlow(int start, int finish) {
         long long cost = 0, flow = 0;
         long long cost = 0, flow = 0;
         while (hasPath(from, to)) {
         while (hasPath(start, finish)) {
             int deltaFlow = bottleneckCapacity(from, to);
             int deltaFlow = bottleneckCapacity(start, finish);
             cost += addFlow(from, to, deltaFlow);
             cost += addFlow(start, finish, deltaFlow);
             flow += deltaFlow;
             flow += deltaFlow;
         }
         }
         return make_pair(cost, flow);
         return { cost, flow };
     }
     }
  };
  };
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);
}


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

Текущая версия от 17:51, 25 июня 2023

class Graph {
    struct Edge {
        int a, b, capacity, flow = 0, cost;

        Edge(int a, int b, int capacity, int cost) :
            a(a), b(b), capacity(capacity), cost(cost) {}

        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 deltaFlow) {
            flow += (v == b ? deltaFlow : -deltaFlow);
        }
    };

    vector<Edge> edges;
    vector<int> distTo;
    vector<int> edgeTo;
    static const int INF = 1e9;

    void fordBellman(int start) {
        fill(distTo.begin(), distTo.end(), INF);
        distTo[start] = 0;
        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 start, int finish) {
        fordBellman(start);
        return distTo[finish] != INF;
    }

    int bottleneckCapacity(int start, int finish) {
        int bCapacity = INF;
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            bCapacity = min(bCapacity, edges[edgeTo[v]].capacityTo(v));
        return bCapacity;
    }

    long long addFlow(int start, int finish, int deltaFlow) {
        long long deltaCost = 0;
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v)) {
            edges[edgeTo[v]].addFlowTo(v, deltaFlow);
            deltaCost += deltaFlow * edges[edgeTo[v]].costTo(v);
        }
        return deltaCost;
    }

public:
    Graph(int vertexCount) :
        distTo(vertexCount), edgeTo(vertexCount) {}
    
    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 start, int finish) {
        long long cost = 0, flow = 0;
        while (hasPath(start, finish)) {
            int deltaFlow = bottleneckCapacity(start, finish);
            cost += addFlow(start, finish, deltaFlow);
            flow += deltaFlow;
        }
        return { cost, flow };
    }
};

Ссылки

Теория:

Код:

Задачи: