RT,萌新不会前向星,所以一直用的邻接表存图,但不知到为什么每当点数大于2×105 的时候,我当最大流板子会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;
}
} ;