Stinger @ 2021-04-09 15:05:56
就是我如果在EK中建了反向边就WA37,不加反向边不仅AC还跑得飞快,请问这是什么原因呢?
加反向边:
#include <cstdio>
#include <queue>
#include <cstring>
#define int long long
const int INF = 1e15;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
int from, to, nxt, cap, flow;
} e[10005];
int head[205], a[205], p[205], tot, s, t;
inline void AddEdge(const int u, const int v, const int w) {
e[++ tot].from = u, e[tot].to = v, e[tot].nxt = head[u], head[u] = tot;
e[tot].flow = 0, e[tot].cap = w;
}
std::queue<int> Q;
int Edmonds_Karp() {
int flow(0);
do {
while (Q.size()) Q.pop();
Q.push(s);
memset(a, 0, sizeof a);
a[s] = INF;
while (Q.size() && !a[t]) {
int u(Q.front());
Q.pop();
for (int i(head[u]); i; i = e[i].nxt) {
const int v(e[i].to);
if (!a[v] && e[i].cap > e[i].flow)
a[v] = min(a[u], e[i].cap - e[i].flow), p[v] = i, Q.push(v);
}
}
for (int i(t); i != s; i = e[p[i]].from)
e[p[i]].flow += a[t], e[p[i] ^ 1].flow -= a[t];
flow += a[t];
} while (a[t]);
return flow;
}
signed main() {
int n, m;
scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
for (int i(1); i <= m; ++ i) {
int u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
AddEdge(u, v, w);
AddEdge(v, u, 0);
}
printf("%lld", Edmonds_Karp());
return 0;
}
不加:
#include <cstdio>
#include <queue>
#include <cstring>
#define int long long
const int INF = 1e15;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
int from, to, nxt, cap;
} e[10005];
int head[205], a[205], p[205], tot, s, t;
inline void AddEdge(const int u, const int v, const int w) {
e[++ tot].from = u, e[tot].to = v, e[tot].nxt = head[u], head[u] = tot, e[tot].cap = w;
}
std::queue<int> Q;
int Edmonds_Karp() {
int flow(0);
while (true) {
while (Q.size()) Q.pop();
Q.push(s);
memset(a, 0, sizeof a);
memset(p, 0, sizeof p);
a[s] = INF;
while (Q.size() && !a[t]) {
int u(Q.front());
Q.pop();
for (int i(head[u]); i; i = e[i].nxt) {
const int v(e[i].to);
if (!a[v] && e[i].cap)
a[v] = min(a[u], e[i].cap), p[v] = i, Q.push(v);
}
}
if (!a[t]) break;
for (int i(t); i != s; i = e[p[i]].from)
e[p[i]].cap -= a[t];
flow += a[t];
}
return flow;
}
signed main() {
int n, m;
scanf("%lld%lld%lld%lld", &n, &m, &s, &t);
for (int i(1); i <= m; ++ i) {
int u, v, w;
scanf("%lld%lld%lld", &u, &v, &w);
AddEdge(u, v, w);
}
printf("%lld", Edmonds_Karp());
return 0;
}
by xzggzh1 @ 2021-04-09 15:10:55
@zhangqs 你的边数有没有初始化为 1
by Stinger @ 2021-04-09 15:11:23
@xzggzh1 我的边数一开始图是空的,tot
是
by xzggzh1 @ 2021-04-09 15:12:37
@zhangqs tot=1 就过了
by Stinger @ 2021-04-09 15:12:54
@xzggzh1 好的,我懂了,我是伞兵,谢谢您。