这份 Dinic 是假的吗？

AC_love @ 2023-09-27 12:55:43

by AC_love @ 2023-09-27 12:55:52

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 10010, M = 200010, INF = 1e15;

struct edge
{
    int ed;
    int len;
    int id;
};

vector <edge> e[N];

int n, m, S, T;
int dep[N], cur[N];

bool bfs()
{
    memset(dep, -1, sizeof dep);
    queue <int> q;
    q.push(S);
    dep[S] = 0;
    while (!q.empty())
    {
        int t = q.front();
        q.pop();
        for (int i = 0; i < e[t].size(); i = i + 1)
        {
            int ed = e[t][i].ed;
            if (dep[ed] == -1 && e[t][i].len)
            {
                dep[ed] = dep[t] + 1;
                q.push(ed);
            }
        }
    }
    memset(cur, 0, sizeof(cur));
    return (dep[T] != -1);
}

int dfs(int st, int limit)
{
    if (st == T)
        return limit;
    for (int i = cur[st]; i < e[st].size(); i = i + 1)
    {
        cur[st] = i;  // 当前弧优化
        int ed = e[st][i].ed;
        if (dep[ed] == dep[st] + 1 && e[st][i].len)
        {
            int t = dfs(ed, min(e[st][i].len, limit));
            if (t)
            {
                e[st][i].len -= t;
                e[ed][e[st][i].id].len += t;
                return t;
            }
        }
    }
    return 0;
}

int dinic()
{
    int r = 0, flow;
    while (bfs()) while (flow = dfs(S, INF)) r += flow;
    return r;
}

signed main()
{
    cin >> n >> m >> S >> T;
    while (m -- )
    {
        int st, ed, len;
        cin >> st >> ed >> len;
        int sti = e[st].size();
        int edi = e[ed].size();
        e[st].push_back((edge){ed, len, edi});
        e[ed].push_back((edge){st, 0, sti});
    }
    cout << dinic();

    return 0;
}

by Michael_Liu @ 2023-09-27 13:07:08

@AC_love 这不太对吧，当前弧优化cur里面记录的应该是上一次走到的边的信息，你这每一次bfs都memset一遍有啥用啊

by 聊机 @ 2023-09-27 13:08:53

@Michael_Liu 没问题，当前弧优化是对于一次dfs的。

by Sharpsmile @ 2023-09-27 13:08:55

@Michael_Liu 草。難道沒有用嗎。

by Michael_Liu @ 2023-09-27 13:10:53

@聊机 @Ranger_HoFr 当前弧优化肯定有用啊，我意思是他这个当前弧优化写的不太对吧

by 聊机 @ 2023-09-27 13:11:19

@AC_love 我之前学的时候还有一个无用点优化之类的，但是好像效果不明显，尤其是加了当前弧以后，就是如果从一个流不为0的点往出流发现返回的流是0，那么就把这个点标记成不可用，这样别的点就不会再调用这个点了

by 聊机 @ 2023-09-27 13:12:02

@Michael_Liu 都说了当前弧是对于一次dfs，你增广完一次不更新不就错了吗

by Michael_Liu @ 2023-09-27 13:16:56

@聊机

我开始仔细看他用的是vector，还好奇为啥每次都把cur设为0而不是每个节点对应的出边呢，后来才反应过来用vector的话0对应的就是每个结点的第一条出边

by 聊机 @ 2023-09-27 13:17:58

@Michael_Liu 呃呃确实我一般也不喜欢用vector。

by Michael_Liu @ 2023-09-27 13:18:17

@聊机 我平时用结构体是这样的：

    if(deep[t]!=-1){
        for(int i=1;i<=n;i++)
        {
            cur[i]=head[i];
        }
        return 1;
    }

我是智力障碍