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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: « #include <stdio.h> #include <algorithm> #include <vector> #include <queue> using namespace std; class Edge { int _a, _b, capacity, flow, cost; publi…»)
 
Нет описания правки
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
  #include <stdio.h>
{|width=100%
  #include <algorithm>
|width=50%|
  #include <vector>
'''Через Форда-Беллмана (F * V * E)'''
#include <queue>
 
using namespace std;
  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;
        }
   
   
class Edge {
         int capacityTo(int v) const {
    int _a, _b, capacity, flow, cost;
            return v == b ? capacity - flow : flow;
public:
        }
    Edge(int a, int b, int capacity, int cost) : _a(a), _b(b), capacity(capacity), flow(0), cost(cost) {}
    int a() const {
        int costTo(int v) const {
        return _a;
            return v == b ? cost : -cost;
    }
        }
    int b() const {
         return _b;
        void addFlowTo(int v, int deltaFlow) {
    }
            flow += (v == b ? deltaFlow : -deltaFlow);
    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 {
    int vertexCount;
     vector<Edge> edges;
     vector<Edge> edges;
    vector<int> distTo;
     vector<int> edgeTo;
     vector<int> edgeTo;
     void fordBellman(int v) {
     bool hasPath(int start, int finish) {
        vector<long long> dist(vertexCount, 1e18);
        edgeTo.assign(vertexCount, -1);
        dist[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)) {
                     distTo[b] = distTo[a] + edges[i].costTo(b);
                 if (edges[i].capacityTo(b) && dist[a] != 1e18 && dist[b] > dist[a] + edges[i].costTo(b)) {
                     dist[b] = dist[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)) {
                     distTo[a] = distTo[b] + edges[i].costTo(a);
                 if (edges[i].capacityTo(a) && dist[b] != 1e18 && dist[a] > dist[b] + edges[i].costTo(a)) {
                     dist[a] = dist[b] + edges[i].costTo(a);
                     edgeTo[a] = i;
                     edgeTo[a] = i;
                     update = 1;
                     update = 1;
                 }
                 }
             }
             }
             if (!update)
             if (!update)
                 break;
                 break;
         }
         }
        return dist[finish] != 1e18;
     }
     }
     bool hasPath(int from, int to) {
         fill(distTo.begin(), distTo.end(), 1 << 30);
     int getMinCapacity(int start, int finish) {
        distTo[from] = 0;
         int minCapacity = 1e9;
        fordBellman(from);
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
         return distTo[to] != 1 << 30;
            minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
         return minCapacity;
     }
     }
    int bottleneckCapacity(int from, int to) {
        int bCapacity = 1 << 30;
     long long addFlow(int start, int finish, int deltaFlow) {
        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;
         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 += 1LL * deltaFlow * edges[edgeTo[v]].costTo(v);
         }
         }
         return deltaCost;
         return deltaCost;
     }
     }
  public:
  public:
     Graph(int verticesCount) {
     Graph(int vertexCount) : vertexCount(vertexCount) {}
        distTo.resize(verticesCount);
        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 = getMinCapacity(start, finish);
             cost += addFlow(from, to, deltaFlow);
             cost += addFlow(start, finish, deltaFlow);
             flow += deltaFlow;
             flow += deltaFlow;
         }
         }
         return make_pair(cost, flow);
         return { cost, flow };
     }
     }
  };
  };
|width=50%|
'''Через Джонсона (V * E + F * E * logV)'''
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 main() {
        int other(int v) const {
    int n;
            return v == a ? b : a;
    scanf("%d", &n);
        }
    Graph g(2 * n + 2);
        int capacityTo(int v) const {
            return v == b ? capacity - flow : flow;
        }
   
   
    int source = 0;
        int costTo(int v) const {
    for (int i = 1; i <= n; i++)
            return v == b ? cost : -cost;
         g.addEdge(source, i, 1, 0);
         }
   
   
    int c;
        void addFlowTo(int v, int deltaFlow) {
    for (int i = 1; i <= n; i++) {
            flow += (v == b ? deltaFlow : -deltaFlow);
        for (int j = n + 1; j <= 2 * n; j++) {
            scanf("%d", &c);
            g.addEdge(i, j, 1, c);
         }
         }
    };
    vector<Edge> edges;
    vector<vector<int>> graph;
    vector<long long> fordBellmanDist;
    vector<int> edgeTo;
    void initFordBellmanDist() {
        fordBellmanDist.assign(graph.size(), 0);
        while (1) {
            bool update = 0;
            for (Edge &edge : edges) {
                int a = edge.a, b = edge.b;
                if (edge.capacityTo(b) && fordBellmanDist[b] > fordBellmanDist[a] + edge.costTo(b)) {
                    fordBellmanDist[b] = fordBellmanDist[a] + edge.costTo(b);
                    update = 1;
                }
                if (edge.capacityTo(a) && fordBellmanDist[a] > fordBellmanDist[b] + edge.costTo(a)) {
                    fordBellmanDist[a] = fordBellmanDist[b] + edge.costTo(a);
                    update = 1;
                }
            }
            if (!update)
                break;
        }
    }
    bool hasPath(int start, int finish) {
        vector<long long> dist(graph.size(), 1e18);
        edgeTo.assign(graph.size(), -1);
        set<pair<long long, int>> q;
        dist[start] = 0;
        q.insert({ 0, start });
        while (!q.empty()) {
            int v = q.begin()->second;
            q.erase(q.begin());
            for (int edgeIndex : graph[v]) {
                int to = edges[edgeIndex].other(v);
                if (!edges[edgeIndex].capacityTo(to))
                    continue;
                long long candidate = dist[v] + edges[edgeIndex].costTo(to) + fordBellmanDist[v] - fordBellmanDist[to];
                if (dist[to] > candidate) {
                    q.erase({ dist[to], to });
                    dist[to] = candidate;
                    edgeTo[to] = edgeIndex;
                    q.insert({ dist[to], to });
                }
            }
        }
        if (dist[finish] == 1e18)
            return 0;
       
        for (int v = 0; v < graph.size(); v++)
            if (dist[v] != 1e18)
                fordBellmanDist[v] += dist[v];
        return 1;
     }
     }
   
   
     int sink = 2 * n + 1;
     int getMinCapacity(int start, int finish) {
    for (int i = n + 1; i <= 2 * n; i++)
        int minCapacity = 1e9;
        g.addEdge(i, sink, 1, 0);
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
        return minCapacity;
    }
   
   
     printf("%lld", g.minCostMaxFlow(source, sink).first);
     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 += 1LL * deltaFlow * edges[edgeTo[v]].costTo(v);
        }
        return deltaCost;
    }
public:
    Graph(int vertexCount) : graph(vertexCount) {}
    void addEdge(int from, int to, int capacity, int cost) {
        edges.push_back(Edge(from, to, capacity, cost));
        graph[from].push_back(edges.size() - 1);
        graph[to].push_back(edges.size() - 1);
    }
    pair<long long, long long> minCostMaxFlow(int start, int finish) {
        initFordBellmanDist();
        long long cost = 0, flow = 0;
        while (hasPath(start, finish)) {
            int deltaFlow = getMinCapacity(start, finish);
            cost += addFlow(start, finish, deltaFlow);
            flow += deltaFlow;
        }
        return { cost, flow };
    }
  };


|}
== Ссылки ==
== Ссылки ==
Теория:
Теория:

Текущая версия от 23:32, 27 сентября 2026

Через Форда-Беллмана (F * V * E) 

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);
        }
    };

    int vertexCount;
    vector<Edge> edges;
    vector<int> edgeTo;

    bool hasPath(int start, int finish) {
        vector<long long> dist(vertexCount, 1e18);
        edgeTo.assign(vertexCount, -1);
        dist[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) && dist[a] != 1e18 && dist[b] > dist[a] + edges[i].costTo(b)) {
                    dist[b] = dist[a] + edges[i].costTo(b);
                    edgeTo[b] = i;
                    update = 1;
                }

                if (edges[i].capacityTo(a) && dist[b] != 1e18 && dist[a] > dist[b] + edges[i].costTo(a)) {
                    dist[a] = dist[b] + edges[i].costTo(a);
                    edgeTo[a] = i;
                    update = 1;
                }
            }

            if (!update)
                break;
        }

        return dist[finish] != 1e18;
    }

    int getMinCapacity(int start, int finish) {
        int minCapacity = 1e9;
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
        return minCapacity;
    }

    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 += 1LL * deltaFlow * edges[edgeTo[v]].costTo(v);
        }
        return deltaCost;
    }

public:
    Graph(int vertexCount) : vertexCount(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 = getMinCapacity(start, finish);
            cost += addFlow(start, finish, deltaFlow);
            flow += deltaFlow;
        }
        return { cost, flow };
    }
};

Через Джонсона (V * E + F * E * logV) 

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<vector<int>> graph;
    vector<long long> fordBellmanDist;
    vector<int> edgeTo;

    void initFordBellmanDist() {
        fordBellmanDist.assign(graph.size(), 0);

        while (1) {
            bool update = 0;

            for (Edge &edge : edges) {
                int a = edge.a, b = edge.b;

                if (edge.capacityTo(b) && fordBellmanDist[b] > fordBellmanDist[a] + edge.costTo(b)) {
                    fordBellmanDist[b] = fordBellmanDist[a] + edge.costTo(b);
                    update = 1;
                }

                if (edge.capacityTo(a) && fordBellmanDist[a] > fordBellmanDist[b] + edge.costTo(a)) {
                    fordBellmanDist[a] = fordBellmanDist[b] + edge.costTo(a);
                    update = 1;
                }
            }

            if (!update)
                break;
        }
    }

    bool hasPath(int start, int finish) {
        vector<long long> dist(graph.size(), 1e18);
        edgeTo.assign(graph.size(), -1);
        set<pair<long long, int>> q;

        dist[start] = 0;
        q.insert({ 0, start });

        while (!q.empty()) {
            int v = q.begin()->second;
            q.erase(q.begin());

            for (int edgeIndex : graph[v]) {
                int to = edges[edgeIndex].other(v);
                if (!edges[edgeIndex].capacityTo(to))
                    continue;

                long long candidate = dist[v] + edges[edgeIndex].costTo(to) + fordBellmanDist[v] - fordBellmanDist[to];
                if (dist[to] > candidate) {
                    q.erase({ dist[to], to });
                    dist[to] = candidate;
                    edgeTo[to] = edgeIndex;
                    q.insert({ dist[to], to });
                }
            }
        }

        if (dist[finish] == 1e18)
            return 0;
        
        for (int v = 0; v < graph.size(); v++)
            if (dist[v] != 1e18)
                fordBellmanDist[v] += dist[v];
        return 1;
    }

    int getMinCapacity(int start, int finish) {
        int minCapacity = 1e9;
        for (int v = finish; v != start; v = edges[edgeTo[v]].other(v))
            minCapacity = min(minCapacity, edges[edgeTo[v]].capacityTo(v));
        return minCapacity;
    }

    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 += 1LL * deltaFlow * edges[edgeTo[v]].costTo(v);
        }
        return deltaCost;
    }

public:
    Graph(int vertexCount) : graph(vertexCount) {}

    void addEdge(int from, int to, int capacity, int cost) {
        edges.push_back(Edge(from, to, capacity, cost));
        graph[from].push_back(edges.size() - 1);
        graph[to].push_back(edges.size() - 1);
    }

    pair<long long, long long> minCostMaxFlow(int start, int finish) {
        initFordBellmanDist();
        long long cost = 0, flow = 0;
        while (hasPath(start, finish)) {
            int deltaFlow = getMinCapacity(start, finish);
            cost += addFlow(start, finish, deltaFlow);
            flow += deltaFlow;
        }
        return { cost, flow };
    }
};

Ссылки

Теория:

Код:

Задачи:

Источник — https://acm.khpnets.info/w39/index.php?title=Максимальный_поток_минимальной_стоимости&oldid=2956