为什么我跑得这么慢

Night_Bringer @ 2020-12-04 13:05:32

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define Min(a, b) ((a) < (b) ? (a) : (b))
void Quick_Read(LL &N) {
    N = 0;
    LL op = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')
            op = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        N = (N << 1) + (N << 3) + (c ^ 48);
        c = getchar();
    }
    N *= op;
}
const LL MAXN = 2e2 + 5;
struct Node {
    LL to, value, rev;
    Node() {}
    Node(LL T, LL V, LL R) {
        to = T;
        value = V;
        rev = R;
    }
};
vector<Node> v[MAXN];
queue<LL> q;
LL de[MAXN], be[MAXN];
LL n, m, s, t;
bool bfs_Dinic() {
    memset(de, 0, sizeof(de));
    while(!q.empty())
        q.pop();
    q.push(s);
    de[s] = 1; be[s] = 0;
    while(!q.empty()) {
        LL now = q.front();
        q.pop();
        LL SIZ = v[now].size();
        for(int i = 0; i < SIZ; i++) {
            LL next = v[now][i].to;
            if(v[now][i].value && !de[next]) {
                q.push(next);
                be[next] = 0;
                de[next] = de[now] + 1;
                if(next == t)
                    return true;
            }
        }
    }
    return false;
}
LL dfs_Dinic(LL now, LL flow) {
    if(now == t)
        return flow;
    int i, surp = flow;
    LL SIZ = v[now].size();
    for(i = be[now]; i < SIZ && surp; i++) {
        LL next = v[now][i].to, valedge = v[now][i].value;
        if(valedge && de[next] == de[now] + 1) {
            LL maxnow = dfs_Dinic(next, Min(surp, valedge));
            if(!maxnow)
                de[next] = 0;
            v[now][i].value -= maxnow;
            v[next][v[now][i].rev].value += maxnow;
            surp -= maxnow;
        }
    }
    be[now] = i;
    return flow - surp;
}
LL Dinic() {
    LL res = 0, flow = 0;
    while(bfs_Dinic())
        while(flow = dfs_Dinic(s, INF))
            res += flow;
    return res;
}
void Read() {
    LL A, B, C;
    Quick_Read(n);
    Quick_Read(m);
    Quick_Read(s);
    Quick_Read(t);
    for(int i = 1; i <= m; i++) {
        Quick_Read(A);
        Quick_Read(B);
        Quick_Read(C);
        LL idA = v[A].size(), idB = v[B].size();
        v[A].push_back(Node(B, C, idB));
        v[B].push_back(Node(A, 0, idA));
    }
}
int main() {
    Read();
    printf("%lld", Dinic());
    return 0;
}

by iorit @ 2020-12-04 13:13:44

while(bfs_Dinic())
        while(flow = dfs_Dinic(s, INF))
            res += flow;

改为

while(bfs_Dinic())
        res += dfs_Dinic(s, INF);

by watermonster @ 2020-12-04 13:16:27

bool bfs_Dinic() {
    memset(de, 0, sizeof(de));
    while(!q.empty())
        q.pop();
    q.push(s);
    de[s] = 1; be[s] = 0;
    while(!q.empty()) {
        LL now = q.front();
        q.pop();
        LL SIZ = v[now].size();
        for(int i = 0; i < SIZ; i++) {
            LL next = v[now][i].to;
            if(v[now][i].value && !de[next]) {
                q.push(next);
                be[next] = 0;
                de[next] = de[now] + 1;
                if(next == t)
                    return true;
            }
        }
    }
    return false;
}

if(next == t)return true;有问题吧？不搜出所有增广路直接return的话复杂度就假了？

by Night_Bringer @ 2020-12-04 13:19:35

谢谢大佬们

by watermonster @ 2020-12-04 13:21:00

而且没加当前弧优化？

by Night_Bringer @ 2020-12-04 13:23:40

都试过了，还是怎么慢

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define Min(a, b) ((a) < (b) ? (a) : (b))
void Quick_Read(int &N) {
    N = 0;
    int op = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')
            op = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        N = (N << 1) + (N << 3) + (c ^ 48);
        c = getchar();
    }
    N *= op;
}
const int MAXN = 2e2 + 5;
struct Node {
    int to, value, rev;
    Node() {}
    Node(int T, int V, int R) {
        to = T;
        value = V;
        rev = R;
    }
};
vector<Node> v[MAXN];
queue<int> q;
int de[MAXN], be[MAXN];
int n, m, s, t;
bool bfs_Dinic() {
    memset(de, 0, sizeof(de));
    while(!q.empty())
        q.pop();
    q.push(s);
    de[s] = 1; be[s] = 0;
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        int SIZ = v[now].size();
        for(int i = 0; i < SIZ; i++) {
            int next = v[now][i].to;
            if(v[now][i].value && !de[next]) {
                q.push(next);
                be[next] = 0;
                de[next] = de[now] + 1;
                if(next == t)
                    return true;
            }
        }
    }
    return false;
}
int dfs_Dinic(int now, int flow) {
    if(now == t)
        return flow;
    int i, surp = flow;
    int SIZ = v[now].size();
    for(i = be[now]; i < SIZ && surp; i++) {
        int next = v[now][i].to, valedge = v[now][i].value;
        if(valedge && de[next] == de[now] + 1) {
            int maxnow = dfs_Dinic(next, Min(surp, valedge));
            if(!maxnow)
                de[next] = 0;
            v[now][i].value -= maxnow;
            v[next][v[now][i].rev].value += maxnow;
            surp -= maxnow;
        }
    }
    be[now] = i;
    return flow - surp;
}
long long Dinic() {
    long long res = 0;
    int flow = 0;
    while(bfs_Dinic())
        while(flow = dfs_Dinic(s, INF))
            res += flow * 1LL;
    return res;
}
void Read() {
    int A, B, C;
    Quick_Read(n);
    Quick_Read(m);
    Quick_Read(s);
    Quick_Read(t);
    for(int i = 1; i <= m; i++) {
        Quick_Read(A);
        Quick_Read(B);
        Quick_Read(C);
        int idA = v[A].size(), idB = v[B].size();
        v[A].push_back(Node(B, C, idB));
        v[B].push_back(Node(A, 0, idA));
    }
}
int main() {
    Read();
    printf("%lld", Dinic());
    return 0;
}

by Night_Bringer @ 2020-12-04 13:25:03

@watermonster 加了弧优化

be[now] = i;

by Night_Bringer @ 2020-12-04 13:26:11

by watermonster @ 2020-12-04 13:34:29

@快乐的水鬼pyke

if(now == t)return flow;

改成 if(now == t || !flow) return flow;试试？

by Night_Bringer @ 2020-12-04 13:41:03

一如既往的慢

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
#define Min(a, b) ((a) < (b) ? (a) : (b))
void Quick_Read(LL &N) {
    N = 0;
    LL op = 1;
    char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-')
            op = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        N = (N << 1) + (N << 3) + (c ^ 48);
        c = getchar();
    }
    N *= op;
}
const LL MAXN = 2e2 + 5;
struct Node {
    LL to, value, rev;
    Node() {}
    Node(LL T, LL V, LL R) {
        to = T;
        value = V;
        rev = R;
    }
};
vector<Node> v[MAXN];
queue<LL> q;
LL de[MAXN], be[MAXN];
LL n, m, s, t;
bool bfs_Dinic() {
    memset(de, 0, sizeof(de));
    while(!q.empty())
        q.pop();
    q.push(s);
    de[s] = 1; be[s] = 0;
    while(!q.empty()) {
        LL now = q.front();
        q.pop();
        LL SIZ = v[now].size();
        for(int i = 0; i < SIZ; i++) {
            LL next = v[now][i].to;
            if(v[now][i].value && !de[next]) {
                q.push(next);
                be[next] = 0;
                de[next] = de[now] + 1;
                if(next == t)
                    return true;
            }
        }
    }
    return false;
}
LL dfs_Dinic(LL now, LL flow) {
    if(now == t || !flow)
        return flow;
    int i, surp = flow;
    LL SIZ = v[now].size();
    for(i = be[now]; i < SIZ && surp; i++) {
        LL next = v[now][i].to, valedge = v[now][i].value;
        if(valedge && de[next] == de[now] + 1) {
            LL maxnow = dfs_Dinic(next, Min(surp, valedge));
            if(!maxnow)
                de[next] = 0;
            v[now][i].value -= maxnow;
            v[next][v[now][i].rev].value += maxnow;
            surp -= maxnow;
        }
    }
    be[now] = i;
    return flow - surp;
}
LL Dinic() {
    LL res = 0, flow = 0;
    while(bfs_Dinic())
        while(flow = dfs_Dinic(s, INF))
            res += flow;
    return res;
}
void Read() {
    LL A, B, C;
    Quick_Read(n);
    Quick_Read(m);
    Quick_Read(s);
    Quick_Read(t);
    for(int i = 1; i <= m; i++) {
        Quick_Read(A);
        Quick_Read(B);
        Quick_Read(C);
        LL idA = v[A].size(), idB = v[B].size();
        v[A].push_back(Node(B, C, idB));
        v[B].push_back(Node(A, 0, idA));
    }
}
int main() {
    Read();
    printf("%lld", Dinic());
    return 0;
}

by smarthehe @ 2020-12-04 13:49:41

  for(i = be[now]; i < SIZ && surp; i++) {
        LL next = v[now][i].to, valedge = v[now][i].value;
        if(valedge && de[next] == de[now] + 1) {
            LL maxnow = dfs_Dinic(next, Min(surp, valedge));
            if(!maxnow)
                de[next] = 0;
            v[now][i].value -= maxnow;
            v[next][v[now][i].rev].value += maxnow;
            surp -= maxnow;
        }
    }
    be[now] = i;

当前弧优化写错了。应该是

  for(i = be[now]; i < SIZ && surp; i++) {
  be[now]=i;
        LL next = v[now][i].to, valedge = v[now][i].value;
        if(valedge && de[next] == de[now] + 1) {
            LL maxnow = dfs_Dinic(next, Min(surp, valedge));
            if(!maxnow)
                de[next] = 0;
            v[now][i].value -= maxnow;
            v[next][v[now][i].rev].value += maxnow;
            surp -= maxnow;
        }
    }