萌新,写假了Dinic,73分,求助

P3376 【模板】网络最大流

CitrusSin @ 2023-02-14 19:36:59

#include <bits/stdc++.h>

using namespace std;
using u64 = uint64_t;

bool dinic_layer_bfs(
    const vector<unordered_map<int, u64>>& graph,
    vector<int>& layer,
    size_t n, int s, int t
) {
    queue<int> nodes;
    nodes.push(s);
    layer[s] = 0;

    int cnt = 0;
    bool result = false;
    while (!nodes.empty()) {
        size_t ql = nodes.size();
        while (ql--) {
            int node = nodes.front();
            nodes.pop();

            if (node == t) result = true;
            for (const pair<int, u64>& conn : graph[node]) {
                if (layer[conn.first] == -1 && conn.second > 0) {
                    nodes.push(conn.first);
                    layer[conn.first] = cnt+1;
                }
            }
        }
        cnt++;
    }

    return result;
}

u64 dinic_extpath_dfs(
    vector<unordered_map<int, u64>>& graph,
    const vector<int>& layer,
    int s, int t, u64 max_flow
) {
    if (s == t) return max_flow;

    int terminate_layer = layer[t];
    u64 total_flow = 0;
    for (pair<const int, u64>& conn : graph[s]) {
        if (
            conn.second > 0 &&
            layer[conn.first] == layer[s]+1 &&
            (layer[conn.first] < terminate_layer || conn.first == t)
        ) {
            u64 flow = dinic_extpath_dfs(graph, layer, conn.first, t, min(max_flow - total_flow, conn.second));
            if (flow > 0) {
                graph[s][conn.first] -= flow;
                graph[conn.first][s] += flow;
                total_flow += flow;
            }
            if (total_flow == max_flow) break;
        }
    }
    return total_flow;
}

u64 max_flow_dinic(const vector<unordered_map<int, u64>>& graph, int s, int t) {
    const u64 INF_U64 = numeric_limits<u64>::max();

    if (s == t) return INF_U64;

    int n = graph.size();
    vector<unordered_map<int, u64>> graph_rev(n);
    for (int i=0; i<n; i++) {
        for (const auto& conn : graph[i]) {
            graph_rev[i][conn.first] += conn.second;
            graph_rev[conn.first][i] += 0;
        }
    }

    u64 flow = 0;
    vector<int> layer(n, -1);
    while (dinic_layer_bfs(graph_rev, layer, n, s, t)) {
        flow += dinic_extpath_dfs(graph_rev, layer, s, t, INF_U64);
        layer.assign(n, -1);
    }

    return flow;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, s, t;
    cin >> n >> m >> s >> t;
    s--, t--;
    vector<unordered_map<int, u64>> graph(n);
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        graph[u][v] = w;
    }

    u64 flow = max_flow_dinic(graph, s, t);
    cout << flow << endl;
    return 0;
}

8,9,10三个点会WA,其余AC,但是由于输入数据过于恐怖,本蒟蒻已经无力debug了


by CitrusSin @ 2023-02-14 19:49:03

一些更加具体的信息:
在第8个测试中期望的正确答案是37381805875,而这个程序给出的答案是32114753220,比正确答案要小


by qizhixiaocangying @ 2023-05-19 19:44:43

可能有重边,重边流量要累加上

while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        graph[u][v] = w;
    }

改为

while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        graph[u][v] += w;
    }

即可。


by CitrusSin @ 2023-05-27 19:41:31

@qizhixiaocangying 非常感谢大佬!当初怎么想都一直以为是算法本身写出了问题,怎么都没想到是重边这块(


|