萌新求助,网络流空间爆炸
  • 板块学术版
  • 楼主MVP_Harry
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/6/23 03:39
  • 上次更新2023/11/4 21:35:53
查看原帖
萌新求助,网络流空间爆炸
306962
MVP_Harry楼主2021/6/23 03:39

RT,萌新不会前向星,所以一直用的邻接表存图,但不知到为什么每当点数大于2×1052 \times10^5 的时候,我当最大流板子会MLE... 按理来说空间应该还可以承受啊,是vector的问题吗?

请大佬们帮我看一下出错的原因以及如何解决,谢谢!

附我的最大流板子以及提交记录

class Edge {
public:
    int to, from, cap, flow;
    Edge(int f, int t, int c, int ff) {
        from = f, to = t, cap = c, flow = ff;
    }
} ;

class Dinic {
private:
    int N, M, S, T;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int cur[maxn];
    int d[maxn];

public:
    Dinic(int n, int m, int s, int t) {
        N = n, M = m, S = s, T = t;
        edges.clear();
        for (int i = 0; i <= n; i++)
            G[i].clear();
    }

    void add_edge(int from, int to, int cap) {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        M = edges.size();
        G[from].push_back(M - 2);
        G[to].push_back(M - 1);
    }

    void print_edge() {
        for (auto e : edges) {
            cout << e.from << " " << e.to << " " << e.cap << "\n";
        }
    }

    bool BFS() {
        memset(vis, 0, sizeof vis);
        queue<int> q;
        d[S] = 0;
        q.push(S);
        vis[S] = true;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int y : G[x]) {
                auto & e = edges[y];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = true;
                    q.push(e.to);
                    d[e.to] = d[x] + 1;
                }
            }
        }
        return vis[T];
    }

    int DFS(int u, int a) {
        if (u == T || a == 0) return a;
        int flow = 0, f;
        for (int & i = cur[u]; i < (int) G[u].size(); i++) {
            auto & e = edges[G[u][i]];
            if (d[u] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[u][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }

    int Maxflow() {
        int flow = 0;
        while (BFS()) {
            memset(cur, 0, sizeof cur);
            flow += DFS(S, INF);
        }
        return flow;
    }
} ;
2021/6/23 03:39
加载中...