重金5块钱求大佬帮忙看一下我这个网络流Dinic算法的实现哪里出问题了?

P3376 【模板】网络最大流

quanjun @ 2022-03-26 21:30:25

按照《ACM国际大学生程序设计竞赛.算法与实现》第89页的dinic模板实现的(稍微改动了一些,但是应该也没有啥问题啊)。求大佬帮忙看一下我的代码实现,并私信我微信或者QQ,我会给第一位解答对的大佬转5元红包,万分感谢!

下面是代码:

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9, maxn = 202, maxm = 10010;

struct Edge {
    int v, f, nxt;
} e[maxm];

int n, m, src, sink, head[maxn], ecnt;

void init() {
    ecnt = 0;
    memset(head, -1, sizeof(int)*(n+1));
}

void addedge(int u, int v, int c) {
    e[ecnt] = {v, c, head[u]}; head[u] = ecnt++;
    e[ecnt] = {u, c, head[v]}; head[v] = ecnt++;
}

queue<int> que;
int dis[maxn];

bool bfs() {
    while (!que.empty())
        que.pop();
    memset(dis, -1, sizeof(int)*(n+1));
    dis[src] = 0;
    que.push(src);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = head[u]; i != -1; i = e[i].nxt) {
            int v = e[i].v;
            if (e[i].f && dis[v]==-1) {
                dis[v] = dis[u] + 1;
                que.push(v);
            }
        }
    }
    return dis[sink] != -1;
}

int dfs(int u, int delta) {
    if (u == sink)
        return delta;
    int res = 0;
    for (int i = head[u]; i != -1 && delta; i = e[i].nxt) {
        int v = e[i].v, f = e[i].f;
        if (f && dis[v] == dis[u] + 1) {
            int dd = dfs(v, min(delta, f));
            e[i].f -= dd;
            e[i^1].f += dd;
            delta -= dd;
            res += dd;
        }
    }
    return res;
}

int maxflow() {
    int res = 0;
    while (bfs())
        res += dfs(src, inf);
    return res;
}

int main() {
    cin >> n >> m >> src >> sink;
    init();
    while (m --) {
        int u, v, w;
        cin >> u >> v >> w;
        addedge(u, v, w);
    }
    cout << maxflow() << endl;
    return 0;
}

by quanjun @ 2022-03-26 21:48:06

@Refined_heart 感谢!


上一页 |