为什么我跑得这么慢

P3376 【模板】网络最大流

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 Night_Bringer @ 2020-12-04 13:54:45

问题解决了,谢谢回答我的大佬们


上一页 |