大佬为啥我9,10一直过不去

P3376 【模板】网络最大流

cjwdyzxfblzs @ 2023-02-23 08:09:46

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3500, INF = 0x3f3f3f3f;

int n, m, s, t;

struct edge
{
    int to, cap, rev; // 终点, 容量, 反向边
};
vector<edge> G[N]; // 图的邻接表表示 
bool used[N];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

inline void add(int from, int to, int cap) // 存边
{
    G[from].push_back((edge){to, cap, G[to].size()});
    G[to].push_back((edge){from, 0, G[from].size() - 1});
}

inline int dfs(int v, int t, int f)
{
    if (v == t) return f;
    used[v] = true;
    for (register int i = 0; i < G[v].size(); ++ i )
    {
        edge &e = G[v][i];
        if (!used[e.to] && e.cap > 0)
        {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0)
            {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

inline int max_flow(int s, int t)
{
    int flow = 0;
    for (;;)
    {
        memset(used, 0, sizeof(used));
        int (f) = dfs(s, t, INF);
        if (f == 0) return flow;
        flow += f;
    }
}

signed main()
{
    n = read(), m = read(), s = read(), t = read();

    for (register int i = 1; i <= m; ++ i )
    {
        register int u, v, w;
        u = read(), v = read(), w = read();
        add(u, v, w);
        add(v, u, 0);
    }

    printf("%ld\n", max_flow(s, t));

    return 0;
}

by _djc_ @ 2023-02-23 10:43:23

天棋已经开始学网络流了吗这么快……

会不会是dfs的原因,用bfs找增广路试试能不能过


by cjwdyzxfblzs @ 2023-02-23 17:25:34

@djc 行,我没咋看Dicnc,感觉这个Folk应该可以过去的,但是很离谱


by _djc_ @ 2023-02-23 17:29:07

@sjzez__chess 您们学的这么快吗……


|