28分MLE求助

P3376 【模板】网络最大流

wumingdeyu @ 2022-10-02 21:36:56


#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
#define ll long long
#define Re register int
using namespace std;

const int M = 5005, N = 205, inf = 0x7f7f7f7f;
int n, m, s, t, x, y, z, head[N], o = 1, cur[N], dis[N];
ll ans;
struct QAQ {
    int v, next;
    ll w;
} a[M * 2];
void read(int &x) {
    int f = 0;
    x = 0;
    char c = getchar();
    while (c <= '0' || c >= '9') f |= c == '-', c = getchar();
    while (c >= '0' || c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    x = f ? -x : x;
}
void add(int x, int y, int z) {
    a[++o].next = head[x], a[o].v = y, a[o].w = z, head[x] = o;
}
bool bfs(int st, int ed) {
    for (int i = 1; i <= n; i++)dis[i] = 0;
    queue<int> Q;
    for (int i = 0; i <= n; i++) {
        cur[i] = head[i], dis[i] = 0;
    }
    dis[st] = 1;
    Q.push(st);
    while (!Q.empty()) {
        //  cout<<'$';
        int x = Q.front(), to = 0;
        Q.pop();
        for (int i = head[x]; i; i = a[i].next) {
            //      cout<<endl<<endl<<endl<<i<<" ";
//          getchar();
            if (a[i].w && !dis[to = a[i].v]) {
                dis[to] = dis[x] + 1, Q.push(to);
                if (to == ed) {
                    return 1;
                }
            }
        }
    }
    return 0;
}
ll dfs(int x, ll val) {
//  cout<<'#';
    if (!val || x == t) return val;
    int temp = 0, to, f;
    for (int i = cur[x]; i; i = a[i].next) {
        cur[x] = i;
        if (dis[to = a[i].v] && (f = dfs(to, min(val - temp, a[i].w)))) {

            a[i].w -= f, a[i ^ 1].w += f;
            temp += f;
            if (temp == val)break;
        }
    }
    return temp;
}
void Dinic(int st, int ed) {
    while (bfs(st, ed)) ans += dfs(st, inf);
}
int main() {
//  read(n),read(m),read(s),read(t);
    cin >> n >> m >> s >> t;
    while (m--) // read(x),read(y),read(z),add(x,y,z),add(y,x,0);
        cin >> x >> y >> z, add(x, y, z), add(y, x, 0);
    Dinic(s, t);
    printf("%lld", ans);
    return 0;
}

by Zaunese @ 2022-11-24 20:34:47

//  cout<<'#';
    if (!val || x == t) return val;
    int temp = 0, to, f;
    for (int i = cur[x]; i; i = a[i].next) {
        cur[x] = i;
        if (dis[to = a[i].v] == dis[x] + 1 && (f = dfs(to, min(val - temp, a[i].w)))) {

            a[i].w -= f, a[i ^ 1].w += f;
            temp += f;
            if (temp == val)break;
        }
    }
    return temp;
}

|