Edmonds Karp算法模板

#include 
#include 
#include 
#include 
using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;
using std::queue;
using std::memset;
using std::min;
using int_t = long long int;

struct Edge {
    int_t from;
    int_t to;
    int_t capacity = 0;
    int_t flow = 0;

    Edge(int_t from, int_t to, int_t capacity, int_t flow) :
    from(from), to(to), capacity(capacity), flow(flow) {
    }

};
vector edges;
vector graph[100000 + 1];

void insertEdge(int_t from, int_t to, int_t capacity) {

    edges.push_back((Edge) {
        from, to, capacity, 0
    });

    edges.push_back((Edge) {
        to, from, 0, 0
    });
    graph[from].push_back(edges.size() - 2);
    graph[to].push_back(edges.size() - 1);
}
int_t n, m, start, target;
int_t minFlow[100000 + 1];
int_t path[100000 + 1];

int main() {
    cin >> n >> m >> start>>target;
    for (int_t i = 1; i <= m; i++) {
        int_t from, to, cap;
        cin >> from >> to>>cap;
        insertEdge(from, to, cap);
    }
    int_t maxFlow = 0;
    while (true) {
        //BFS
        queue qu;
        qu.push(start);
        memset(minFlow, 0, sizeof (minFlow));
        minFlow[start] = 0x7fffffff;
        memset(path, 0, sizeof (path));
        while (qu.empty() == false) {
            int_t x = qu.front();
            qu.pop();
            for (int_t edgeId : graph[x]) {
                Edge& edge = edges[edgeId];
                if (minFlow[edge.to] == 0 && edge.flow < edge.capacity) {
                    minFlow[edge.to] = min(minFlow[x], edge.capacity - edge.flow);
                    qu.push(edge.to);
                    path[edge.to] = edgeId;
                }
            }
            if (minFlow[target]) {
                break;
            }
        }
        if (minFlow[target] == 0)break;
        //       cout << "一条增广路" << endl;
        for (int_t v = target; v != start; v = edges[path[v]].from) {
            edges[path[v]].flow += minFlow[target];
            edges[path[v]^1].flow -= minFlow[target];
            //     cout << v << " <- ";
        }
        // cout << start<
共享此文章：
点击分享到Twitter（在新窗口中打开）
点击分享到 Facebook （在新窗口中打开）
赞过：
赞 正在加载……