Dinic算法求助
查看原帖
Dinic算法求助
917922
orekix楼主2023/2/3 18:42

想请问一下各位大佬我这段dinic算法哪里写的有问题吗,只能通过部分测试点,自己排错半天没发现哪里有错。

#include <bits/stdc++.h>

using namespace std;

class Edge {
public:
    int to;
    long long weight;
    int next;

    Edge(int to, long long weight, int next) : to(to), weight(weight), next(next) {}

    Edge() {};
};

int m, n, S, T, cnt = 1;
vector<Edge> graph;
vector<int> level, head;

void addEdge(int from, int to, long long weight) {
    graph[++cnt] = Edge(to, weight, head[from]);
    head[from] = cnt;
}

bool bfs() {
    level = vector<int>(n, 0);
    level[S] = 1;
    queue<int> queue;
    queue.emplace(S);
    while (!queue.empty()) {
        int u = queue.front();
        queue.pop();
        for (int i = head[u]; i; i = graph[i].next) {
            int v = graph[i].to;
            long long weight = graph[i].weight;
            if (!level[v] && weight) {
                level[v] = level[u] + 1;
                if (v == T) return true;
                queue.emplace(v);
            }
        }
    }
    return false;
}

long long dfs(int u, long long inFLow) {
    if (u == T) return inFLow;
    long long outFlow = 0;
    for (int i = head[u]; i; i = graph[i].next) {
        int v = graph[i].to;
        long long weight = graph[i].weight;
        if (level[v] == level[u] + 1 && weight) {
            long long flow = dfs(v, min(weight, inFLow));
            graph[i].weight -= flow;
            graph[i ^ 1].weight += flow;
            inFLow -= flow;
            outFlow += flow;
            if (!inFLow) break;
        }
    }
    if (outFlow == 0) level[u] = 0;
    return outFlow;
}

long long dinic() {
    long long maxFlow = 0;
    while (bfs()) {
        maxFlow += dfs(S, LONG_LONG_MAX);
    }
    return maxFlow;
}

int main() {
    cin >> n >> m >> S >> T;
    head = vector<int>(n + 1, 0);
    graph = vector<Edge>(2 * m + 2);
    for (int i = 0; i < m; ++i) {
        int from, to, weight;
        cin >> from >> to >> weight;
        addEdge(from, to, weight);
        addEdge(to, from, 0);
    }
    cout << dinic();
}
2023/2/3 18:42
加载中...