重金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 Raymondzll @ 2022-03-26 21:33:04

@quanjun longlong的问题吧,不确定


by ningago @ 2022-03-26 21:33:47

@quanjun

你用了e[i^1].f,所以01,23是一组,ecnt = 1就行了(吧)


by 7KByte @ 2022-03-26 21:34:41

@ningago 他的边是0开始编号的好吧


by ningago @ 2022-03-26 21:35:20

@7KByte 我瞎了,++idx人再此


by 7KByte @ 2022-03-26 21:36:25

@quanjun long long的问题,还有连边时反向边的容量应该是0


by wkywkywky @ 2022-03-26 21:40:28

@7KByte 加了只有91


by Refined_heart @ 2022-03-26 21:43:39

@quanjun 加上当前弧过了


by quanjun @ 2022-03-26 21:46:11

@7KByte 谢谢大佬,之前提交过这道题,发现这次数据又加强了,原来是反边为0的问题,改过来之后有一组数据TLE了,不过已经解决了我的疑问,十分感谢,5元红包私聊您哈


by quanjun @ 2022-03-26 21:46:58

@Refined_heart 请问什么是当前弧哈,大佬可以发一下你的代码吗?


by Refined_heart @ 2022-03-26 21:47:23

@quanjun 刚刚已经给你私信过去了


| 下一页