Dinic算法求助

P3376 【模板】网络最大流

orekix @ 2023-02-03 18:42:26

想请问一下各位大佬我这段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();
}

by Code_quantum @ 2023-02-03 18:56:03

首先，你在long long和int 的转化上有问题，全改成long long 后82分 @orekix

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class Edge {
public:
    ll to;
    ll weight;
    ll next;

    Edge(ll to, ll weight, ll next) : to(to), weight(weight), next(next) {}

    Edge() {};
};

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

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

bool bfs() {
    level = vector<ll>(n, 0);
    level[S] = 1;
    queue<ll> queue;
    queue.emplace(S);
    while (!queue.empty()) {
        ll u = queue.front();
        queue.pop();
        for (int i = head[u]; i; i = graph[i].next) {
            ll v = graph[i].to;
            ll 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(ll u, long long inFLow) {
    if (u == T) return inFLow;
    long long outFlow = 0;
    for (ll i = head[u]; i; i = graph[i].next) {
        ll 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));
            if(!flow) level[v]=0;
            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<ll>(n + 1, 0);
    graph = vector<Edge>(2 * m + 2);
    for (int i = 0; i < m; ++i) {
        ll from, to; long long weight;
        cin >> from >> to >> weight;
        addEdge(from, to, weight);
        addEdge(to, from, 0);
    }
    cout << dinic();
}

by Code_quantum @ 2023-02-03 18:56:40

剩下的再帮你看一下

by Code_quantum @ 2023-02-03 18:58:19

OK,通过了bfs里面的初始化有一点小问题 @orekix

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class Edge {
public:
    ll to;
    ll weight;
    ll next;

    Edge(ll to, ll weight, ll next) : to(to), weight(weight), next(next) {}

    Edge() {};
};

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

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

bool bfs() {
    level = vector<ll>(n+1, 0);
    level[S] = 1;
    queue<ll> queue;
    queue.emplace(S);
    while (!queue.empty()) {
        ll u = queue.front();
        queue.pop();
        for (int i = head[u]; i; i = graph[i].next) {
            ll v = graph[i].to;
            ll 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(ll u, long long inFLow) {
    if (u == T) return inFLow;
    long long outFlow = 0;
    for (ll i = head[u]; i; i = graph[i].next) {
        ll 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));
            if(!flow) level[v]=0;
            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<ll>(n + 1, 0);
    graph = vector<Edge>(2 * m + 2);
    for (int i = 0; i < m; ++i) {
        ll from, to; long long weight;
        cin >> from >> to >> weight;
        addEdge(from, to, weight);
        addEdge(to, from, 0);
    }
    cout << dinic();
}

by orekix @ 2023-02-03 19:16:26

@Code_quantum 谢谢大佬，没注意到是因为level数组初始化大小开始是从0开始的，后来改成从1开始但是忘改数组大小了o(╥﹏╥)o 。

by reveal @ 2023-02-03 19:32:29

@orekix 但是这个 Dinic 没有当前弧优化，时间复杂度是假的。